python 实现·十大排序算法之希尔排序 (Shell Sort)

关注

发布于: 2020 年 05 月 26 日

简介﻿
希尔排序(Shell Sort)属于插入排序的一种，也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。其基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下，效率是很高的，因此希尔排序在时间效率比直接插入排序有较大提高。
算法实现步骤﻿
选择一个增量序列t1​,t2​,⋯,tk​，其中tk​=1(增量的取法：ti​=2in​)；
按增量序列个数k，对序列进行k 趟排序；
每趟排序根据对应的增量ti​，将待排序列分割成若干长度为m的子序列，分别对各子序列进行直接插入排序。当增量因子为1 时，整个序列作为一个序列来处理，排序完成。
Python 代码实现﻿
# shell_sort 代码实现
from typing import List
def shell_sort(arr:List[int]):
    """
    希尔排序
    :param arr: 待排序的List
    :return: 希尔排序是就地排序(in-place)
    """
    length = len(arr)
    dist = length // 2
    
    while dist > 0:
        for i in range(dist, length):
            temp = arr[i]
            j = i
            while j >= dist and temp < arr[j-dist]:
                arr[j] = arr[j-dist]
                j -= dist
            arr[j] = temp
        dist //= 2
﻿
# 测试数据
if __name__ == '__main__':
    import random
    random.seed(54)
    arr = [random.randint(0,100) for _ in range(10)]
    print("原始数据：", arr)
    shell_sort(arr)
    print("希尔排序结果：", arr)
﻿
# 输出结果
原始数据： [17, 56, 71, 38, 61, 62, 48, 28, 57, 42]
希尔排序结果： [17, 28, 38, 42, 48, 56, 57, 61, 62, 71]
动画演示
算法分析时间复杂度
当一开始为顺序时，效率最高，时间复杂度最好，为O(nlog2​n)；当一开始为逆序时，效率最低，时间复杂度最坏，为O(n2)。希尔排序的时间复杂度是取决于增量的选取，用预不同的序列，时间复杂度可能不同，较快完成排序的平均时间复杂度为O(n1.3)。
空间复杂度
空间复杂度就是在交换元素时那个临时变量所占的内存空间，所以空间复杂度为O(1)。
稳定性
希尔排序需要进行多次插入排序，在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。
综合评价
﻿
联系我们﻿
个人博客网站：http://www.bling2.cn/
Github地址：https://github.com/lb971216008/Use-Python-to-Achieve
知乎专栏：https://zhuanlan.zhihu.com/Use-Python-to-Achieve
小专栏：https://xiaozhuanlan.com/Use-Python-to-Achieve
博客园：https://www.cnblogs.com/Use-Python-to-Achieve
﻿