给出如下关键字序列{50,26,38,80,70,90,8,30,40,20}的希尔排序过程,增量序列为d={5,3,1}。排序结果为从小到大
时间: 2023-08-19 16:03:53 浏览: 102
首先,按照增量序列d={5,3,1},将关键字序列分成多个子序列,每个子序列的元素个数为n/d,其中n是关键字序列的长度。则按照这个增量序列,将关键字序列分成以下3个子序列:
{50,40},{26,20,30},{38,80,70,90,8}
对每个子序列进行插入排序,得到:
{40,50},{20,26,30},{8,38,70,80,90}
接下来按照增量序列d={3,1},将关键字序列分成多个子序列,每个子序列的元素个数为n/d,其中n是关键字序列的长度。则按照这个增量序列,将关键字序列分成以下2个子序列:
{40,20,8,70},{50,26,30,80,38,90}
对每个子序列进行插入排序,得到:
{8,20,40,70},{26,30,38,50,80,90}
最后按照增量序列d={1},对整个关键字序列进行插入排序,得到最终的排序结果:
{8,20,26,30,38,40,50,70,80,90}
相关问题
设一个关键字序列为{3, 17, 12, 61, 8, 70, 97, 75, 53, 26, 54, 61*},分别写出直接插入排序、希尔排序、快速排序的排序过程。
好的,我会按照您的要求回答问题。以下是对所提到的三种排序算法的排序过程:
1. 直接插入排序
首先,将第一个元素3看作已经排好序的序列。然后从第二个元素17开始,与前面已经排好序的元素进行比较。由于17大于3,所以17放在3的后面,目前序列变为{3, 17, 12, 61, 8, 70, 97, 75, 53, 26, 54, 61*}。接着,将第三个元素12与前面排好序的元素进行比较,发现12小于17,因此将12插入到17的前面,目前序列变为{3, 12, 17, 61, 8, 70, 97, 75, 53, 26, 54, 61*}。以此类推,将后面的元素依次插入到已排好序的序列中,最终得到的有序序列为{3, 8, 12, 17, 26, 53, 54, 61, 61*, 70, 75, 97}。
2. 希尔排序
首先,选择一个增量(gap)序列,本例中使用的是{4, 2, 1}。将序列按照增量分组,对每组使用直接插入排序。首先,以4为增量,将序列分为3组,分别为{3, 8, 54, 97}、{17, 70, 53, 61*}和{12, 75, 26, 61}。对每组使用直接插入排序,得到的序列为{3, 8, 12, 26, 17, 53, 54, 61*, 70, 75, 97, 61}。然后,以2为增量,将序列分为6组,分别为{3, 12, 17, 54, 70, 97}、{8, 26, 53, 61, 75, 61*}。对每组使用直接插入排序,得到的序列为{3, 8, 12, 17, 26, 53, 54, 61, 61*, 70, 75, 97}。最后,以1为增量,对整个序列使用直接插入排序,得到的有序序列同上。
3. 快速排序
首先,选择一个基准值,本例中选择第一个元素3作为基准值。将序列分为两部分,左边部分全部小于基准值,右边部分全部大于基准值。具体过程如下:
{3, 17, 12, 61, 8, 70, 97, 75, 53, 26, 54, 61*}
{3, 17, 12, 8, 26, 54, 53} 61 {70, 97, 75, 61*}
对左边部分{3, 17, 12, 8, 26, 54, 53}重复上述过程,选择第一个元素3作为基准值。分为两部分:
{3, 17, 12, 8} 26 {54, 53}
{3, 12, 8} 17 {} 26 {54, 53}
{3, 8} 12 {} 17 {} 26 {54, 53}
最终得到左边部分的有序序列{3, 8, 12, 17, 26, 53, 54}。对右边部分{70, 97, 75, 61*}重复上述过程,选择第一个元素70作为基准值。分为两部分:
{70, 97, 75} 61* {}
{70, 75} 97 {} 61*
最终得到右边部分的有序序列{61, 70, 75, 97}。将左右两部分合并得到的有序序列为{3, 8, 12, 17, 26, 53, 54, 61, 70, 75, 97, 61*},其中61*是原序列中的重复元素。
设待排序的记录数的关键字序列为{47,55,10,80,15,5,30,70,47,40},增量序列为{5、3、1}用希尔排序进行排序
希尔排序是插入排序的一种高效率的改进版本,其主要思想是将待排序序列分为若干个子序列,对每个子序列分别进行插入排序,然后逐步减少子序列的长度,最终使整个序列成为一个有序序列。
根据增量序列{5、3、1},我们可以先将待排序序列分为5个子序列,分别为{47,5}、{55,30}、{10,70}、{80,47}、{15,40},对这5个子序列分别进行插入排序,得到{5,47}、{30,55}、{10,70}、{47,80}、{15,40},然后将增量减小为3,再次分为3个子序列,分别为{5,30,15}、{47,70,40}、{47,55,10},对这3个子序列分别进行插入排序,得到{5,15,30}、{40,47,70}、{10,47,55},最后将增量减小为1,对整个序列进行插入排序,得到最终结果{5,10,15,30,40,47,47,55,70,80}。
下面是希尔排序的实现代码,使用 Python 编写:
```python
def shell_sort(arr, incs):
for inc in incs:
for i in range(inc, len(arr)):
j = i
temp = arr[i]
while j >= inc and arr[j - inc] > temp:
arr[j] = arr[j - inc]
j -= inc
arr[j] = temp
return arr
arr = [47, 55, 10, 80, 15, 5, 30, 70, 47, 40]
incs = [5, 3, 1]
sorted_arr = shell_sort(arr, incs)
print(sorted_arr)
```
输出结果为:[5, 10, 15, 30, 40, 47, 47, 55, 70, 80]