【算法】希尔排序 Shell Sort

算法介绍

希尔排序，用来解决插入排序的不足：每次只能将数据往后挪动一个位置，不能往后挪动到一个比较远的位置；用gap表示数据挪动的距离，在插入排序中，gap一直等于1，在最坏情况下，将第一个数挪动最后一个位置需要挪动 n-1 次，为方便理解，用“1位插入排序”表示“插入排序”。
希尔排序中先将gap设置为一个比较大的值，进行一次“gap位插入排序”，然后将gap变小，进行一次“gap位插入排序”，不断迭代，直到gap不大于0。
gap变化过程如下：首先将gap设置为 n//meta (meta通常为质数2)，然后下次将gap设置为 gap//meta，不断重复直到gap不大于0。gap更多变化方法

视频演示

首推： https://www.youtube.com/watch?v=SHcPqUe2GZM

如果看不了可以看这个 https://www.bilibili.com/video/av64424835

python代码

#-*- coding: utf-8 -*-

def shell_sort(data):
    meta = 2
    n = len(data)
    gap = int(n//meta)
    while gap>0:
        for i in range(gap, n):
            cur_data = data[i]
            j = i-gap
            while j>=0 and cur_data<data[j]:
                data[j+gap] = data[j]
                j -= gap
            data[j+gap] = cur_data
        gap = int(gap//meta)
    return data

if __name__ == '__main__':
    data = [7, 8, 5, 2, 4, 6, 3]
    sorted_data = shell_sort(data.copy())
    print("排序前：", data)
    print("排序后：", sorted_data)

算法分析

最好情况下，数据刚好是升序，比较次数为 S=sum(n-gap) while gap>0 , S< n(n-1)/2 挪动次数为 0;

最坏情况下，数据刚好是降序，比较次数为 S=(2*n-(k+1)*gap)/2 while gap>0, k*gap < n < (k+1)*gap， 挪动次数为 S

希尔排序是插入排序的改进版本，效率比插入排序更高。
希尔排序是不稳定的排序算法，最小时间复杂度为：O(nlogn)，最大时间复杂度为：O(n^2)

希尔排序空间复杂度：O(1)