数据结构之希尔排序

数据结构之希尔排序

希尔排序是插入排序的一种，也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次使用更长的列（步长更长了，列数更少了）来进行。最终整个表就只有一列了。将数组转换至表是为了更好的理解这算法，算法本身还是使用数组进行排序。

希尔排序算法分析

例如，假设这样的一组数[13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10]，如果以步长为5开始进行排序，可以通过将这列表放在有5列的表中来更好的描述算法，这样它们就应该看起来是这样的（竖着的元素是步长组成）：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后对每列进行排序

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字，依次接在一起时我们得到：[10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45]。这时10已经移至正确的位置了，然后再以3为步长进行排序

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之后变为：

10 14 13
25 23 23
27 25 59
39 65 73
45 94 82
94

依序接在一起时我们得到：[10 14 13 25 23 23 27 25 59 39 65 73 45 94 82 94]。然后再以1为步长进行排序。此时就是简单的插入排序了。

简述：是插入排序的高效实现，通过对插入排序减少移动次数来实现。因为如果序列本身已基本有序，则插入排序在进行前后插入时的许多移动所需的重复操作都可以避免。

时间复杂度 希尔排序算法实现

总长length，初始gap(间隔)0=length / 2, 对这gap组分别做插入排序。继续如上操作gap1=gap0 / 2 (向下取整)，继续直至gap n = 1

def shell_sort(li):
    """希尔排序"""
    n = len(li)
    gap = n // 2
    while gap > 0:
        # 希尔排序与插入排序区别核心在于gap
        for i in range(gap, n):
            j = i
            while j > 0:
                if li[j] < li[j - gap]:
                    li[j], li[j - gap] = li[j - gap], li[j]
                    j -= gap
                else:
                    break
        # 缩短步长
        gap //= 2


if __name__ == '__main__':
    li = [54, 26, 93, 17, 77, 31, 44, 50, 20]
    print('排序前：', li)
    shell_sort(li)
    print('排序后：', li)

运行结果：