Python实现希尔排序

Python实现希尔排序

一、希尔排序简介

希尔排序(Shell's Sort)，也被称为递减增量排序算法(Diminishing Increment Sor)，是插入排序的一种更高效的改进排序算法。

插入排序参考：https://blog.csdn.net/weixin_43790276/article/details/104033635

希尔排序是先取一个小于待排序列表长度的正整数d1，把所有距离为d1的数据看成一组，在组内进行插入排序。然后取一个小于d1的正整数d2，继续用d2分组和进行组内插入排序。每次取的分组距离越来越小，组内的数据越来越多，直到di=1，所有数据被分成一组，再进行插入排序，则列表排序完成。

希尔排序是基于插入排序进行优化的排序算法。在插入排序中，如果数据几乎已经排好序时，效率是很高的(想一下抓牌和插牌)，时间复杂度为 O(n) 。但数据的初始状态并不一定是“几乎已经排好序”的，用插入排序每步只能将待插入数据往前移动一位，而希尔排序将数据分组后，每次可以往前移动di位，在di>1时进行的分组和组内排序可以将数据变成“几乎排好序”的状态，此时再进行最后一次插入排序，提高效率。

二、希尔排序原理

希尔排序的原理如下：

1. 选择小于待排序列表长度 n 的正整数序列 d1，d2，...，di，其中 n>d1, d(i-1)>di,  di=1 ，作为数据的间隔距离对列表进行分组。这里对 di 的取值和个数没有要求，只要是整数，d1<n，依次变小即可。

2. 依次用 d1, ..., di 作为数据的距离对列表进行分组和组内插入排序，一共需要进行 i 轮排序。

3. 在最后一轮排序前，列表中的数据达到了“几乎排好序”的状态，此时进行最后一轮插入排序。

以列表 [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] 进行升序排列为例。列表的初始状态如下图。

要进行升序排列，则分组后所有组内插入排序都进行升序排列。本例中以列表长度的1/3作为初始的分组距离 d1 ，d1=4。

1. 从列表的开头开始，对所有数据按 d1 作为距离进行分组，分组只保证数据的间隔距离相等，不保证每组的数据个数一样，只是本例中刚好每组数据一样多。本例的数据可以分为4组，下图中标记了第一组。

2. 对第一组进行组内插入排序，此时的组内插入排序一次可以往前移动 4 位，第一组排序完成后如下图。

3. 对第二组也进行组内插入排序。

4. 第二组排序完成后如下图。

5. 重复对所有分组进行组内插入排序，所有的分组都完成组内排序后，第一轮排序完成，如下图，现在整个列表中的数据更接近“几乎排好序”的状态。

6. 第二轮排序的间隔距离取上一轮的距离除3(地板除取整)，所以第二轮排序时，d2=1，这已经是最后一轮排序了。距离为1，即将所有数据进行插入排序。

先将第一个数据作为已排序序列，后面的数据作为未排序序列，然后依次将未排序序列中的数据插入到已排序序列中。

7. 将5插入已排序序列中，10大于5，交换位置。

8. 继续对整个列表进行插入排序，经过了希尔排序的第一轮排序后，列表更接近“几乎排好序”的状态，排序效率更高。排序结果如下图。

三、Python实现希尔排序

# coding=utf-8
def shell_sort(array):
    interval = int(len(array)/3)
    while interval > 0:
        for i in range(interval, len(array)):
            cur_index = i - interval
            while cur_index >= 0 and array[cur_index] > array[cur_index+interval]:
                array[cur_index+interval], array[cur_index] = array[cur_index], array[cur_index+interval]
                cur_index -= interval
        interval = int(interval/3)
    return array


if __name__ == '__main__':
    array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
    print(shell_sort(array))

运行结果：

[5, 7, 10, 15, 17, 21, 24, 27, 30, 36, 45, 50]

代码中的 interval 表示每次分组时的距离，i 从索引为 interval 的数据开始取值，向前进行插入排序。cur_index 用于标记组内插入排序时待插入数据的索引位置，如果需要交换位置，则 cur_index 每次向前移动 interval 位。

代码中的排序是按轮进行的( interval 变化一次为一轮排序)，而不是一组一组地进行插入排序( i 变化改变插入排序的分组)。

四、希尔排序的时间复杂度和稳定性

1. 时间复杂度

希尔排序的时间复杂度没有插入排序那么直观，因为在希尔排序中，对数据进行分组排序的增量序列是不确定的。这里我们参考前人总结的经验，希尔排序的时间复杂度为 O(n^1.5) 。

希尔排序每进行一轮排序，数据的状态都更接近于有序的状态，经过前面的排序后，最后一轮进行插入排序时，数据接近于最优的状态，所以希尔排序对插入排序在效率上有较大的改进。从时间复杂度也能看出，插入排序的时间复杂度是 O(n^2) ，希尔排序的时间复杂度是 O(n^1.5) 。

希尔排序需要进行多少次排序，完全取决于选择了多少个 di，i 越大，需要进行的排序轮数越多，最后一次排序前也越接近“几乎排好序”的状态。为了排序效率，i 的大小要根据待排序的列表长度进行选择，i 不应该过大，否则排序的轮次太多，有些轮次对于改善数据的排序状态效果很小。i 也不应该过小，i 很小就接近于直接进行插入排序，没有起到对插入排序的优化作用。通常情况下 d1 取待排序列表长度的一半，然后依次减半(减半时会取整，所以不一定都是倍数)，直到 di=1 。

2. 稳定性

在希尔排序中，会进行多次分组插入排序，每一次组内的插入排序是稳定的，不会改变元素的相对次序。但在多次的分组排序中，相同的元素在各自的组内插入排序中移动，相对次序很可能会被打乱。所以希尔排序是一种不稳定的排序算法。

 

 

本文地址：https://blog.csdn.net/weixin_43790276/article/details/104033649