Python希尔排序算法

希尔排序,又叫“缩小增量排序”,是对插入排序进行优化后产生的一种排序算法。它的执行思路是:把数组内的元素按下标增量分组,对每一组元素进行插入排序后,缩小增量并重复之前的步骤,直到增量到达 1。

一般来说,希尔排序的时间复杂度为 O(n1.3)~O(n2),它视增量大小而定。希尔排序的空间复杂度是 O(1),它是一个不稳定的排序算法。进行希尔排序时,元素一次移动可能跨越多个元素,从而可能抵消多次移动,提高了效率。

下面是使用(数组长度/2)作为初始增量的升序希尔排序,每一轮排序过后,增量都缩小一半。

1) 如图 1 所示,从第一个元素开始,以增量 4 来分组。可以看出,当增量为 4 时,一组内只有两个元素,否则元素的下标就超出了数组的范围。
第一轮第一步
图 1:第一轮第一步

2) 如图 2 所示,对组内的元素进行插入排序。
第一轮第二步
图 2:第一轮第二步

3) 如图 3 所示,继续用相同的方法分组,对组内的元素进行插入排序使得它们有序。
完成第一轮排序
图 3:完成第一轮排序
 
整个数组内的数都被遍历完成后,这一轮排序就结束了。把增量缩小一半,继续进行下一轮排序。

4) 如图 4 所示,增量为 2 时,可以看出每一组内的元素增多了,组的总数减少了。继续对每一组内的元素进行插入排序,直到每一组都遍历完成。
第二轮排序
图 4:第二轮排序

5) 最后一轮排序如图 5 所示,再次把增量缩小一半;这时增量为 1,相当于对整个数组进行插入排序,也就是最后一轮排序。
 第三轮排序
图 5:第三轮排序

最后一轮排序结束后,整个希尔排序就结束了。

希尔排序代码:
nums = [5,3,6,4,1,2,8,7]
def ShellSort(nums):
    step = len(nums)//2         #初始化增量为数组长度的一半
    while step > 0:           #增量必须是大于0的整数
        for i in range(step,len(nums)): #遍历需要进行插入排序的数
            ind = i
            while ind >= step and nums[ind] < nums[ind-step]: #对每组进行插入排序
                nums[ind],nums[ind-step] = nums[ind-step],nums[ind]
                ind -= step
        step //= 2           #增量缩小一半
    print(nums)
ShellSort(nums)
运行程序,输出结果为:

[1,2,3,4,5,6,7,8]


在 for 循环中,由于每组的第一个元素不用进行插入排序,而它们的下标处于 0~step-1,所以从下标 step 开始遍历。

需要注意的是,如果要模拟流程图中的做法,要使用两个循环:先分组,然后一次性使同组内的元素有序。为了提高效率,我们直接使用一个 for 循环,每遍历到一个数,就对它所在的组进行插入排序。这样遍历同样符合插入排序的顺序要求。在插入排序中,要改变当前下标的值,所以使用变量 ind 存储当前下标,防止影响 for 循环。

普通插入排序等同于增量为 1 的希尔排序,跨元素的希尔排序实际上只改变了增量,逻辑上与普通插入排序没有区别。