希尔排序（Python实现）

原理

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
希尔排序是把数据按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

时间复杂度

希尔排序是一种不稳定的排序方法，时间复杂度为：O(n^（1.3—2）)。

Python实现

# -*- coding:utf-8 -*-
# 希尔排序

def shell_sort(list):
    n = len(list)
    step = n // 2
    while step > 0: # 最后的步长为1，此时就是一个标准的插入排序
        for cur in range(step, n):
            i = cur
            while i >= step and list[i-step] > list[i]:
                list[i - step], list[i] = list[i], list[i-step]
                i -= step
        step = step // 2
    return list


list = [54, 26, 93, 17, 77, 3, 31, 44, 55, 20]
print(shell_sort(list))