希尔排序算法 #

1. 希尔排序算法介绍
2. 希尔排序算法原理
3. 希尔排序算法的实现

收获 #

学完本节内容，可以初步理解并掌握希尔排序算法。

希尔排序算法介绍 #

希尔排序(Shell’s Sort)，也被称为递减增量排序算法(Diminishing Increment Sort)，是插入排序的一种更高效的改进排序算法。
希尔排序是先取一个小于待排序列表长度的正整数d1，把所有距离为d1的数据看成一组，在组内进行插入排序。然后取一个小于d1的正整数d2，继续用d2分组和进行组内插入排序。每次取的分组距离越来越小，组内的数据越来越多，直到di=1，所有数据被分成一组，再进行插入排序，则列表排序完成。

希尔排序算法原理 #

希尔排序的原理如下：

1. 选择小于待排序列表长度 n 的正整数序列 d1，d2，…，di，其中 n>d1, d(i-1)>di, di=1 ，作为数据的间隔距离对列表进行分组。这里对 di 的取值和个数没有要求，只要是整数，d1<n，依次变小即可。
2. 依次用 d1, …, di 作为数据的距离对列表进行分组和组内插入排序，一共需要进行 i 轮排序。
3. 在最后一轮排序前，列表中的数据达到了“几乎排好序”的状态，此时进行最后一轮插入排序。
   • 
     • 

希尔排序算法的实现 #

python实现代码如下：

def shell_sort(a):
    interval = int(len(a) / 3) #初始排序间隔/3
    while interval > 0:
        for i in range(interval, len(a)):
            cur_index = i - interval
            while cur_index >= 0 and a[cur_index] > a[cur_index + interval]:
                a[cur_index + interval], a[cur_index] = a[cur_index], a[cur_index + interval] #排序交换
                cur_index -= interval
        interval = int(interval / 3) #每次排序间隔/3，循环
    return a


if __name__ == '__main__':
    a=[10,17,50,7,30,15,5,38,21]
    print(shell_sort(a))

小结 #

理解并掌握希尔排序算法的原理
掌握希尔排序的代码实现

习题 #

1. 习题1：画出希尔排序算法的流程图
2. 习题2：使用希尔排序算法，对列表[10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]进行升序排列