python实现【希尔排序】(Shell Sort)

算法原理及介绍

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。

算法过程描述

1. 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

2. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

3. 按增量序列个数k，对序列进行k 趟排序；

4. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

算法排序图解如下

希尔.gif

python实现代码

def shell_sort(array):
    n = len(array)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            for j in range(i, gap-1, -gap):
                if array[j] < array[j-gap]:
                    array[j], array[j-gap] = array[j-gap], array[j]
                else:
                    break
        gap //= 2
    return array

如果喜欢作者，欢迎点赞、收藏及关注，谢谢！
点击下面相应的链接即可查看各个算法的详细介绍及python实现方法：

1. 冒泡排序(BubbleSort)
2. 选择排序(SelectionSort)
3. 插入排序(InsertSort)
4. 归并排序(MergeSort)
5. 快速排序(QuickSort)
6. 堆排序(Heap Sort)
7. 计数排序(Count Sort)
8. 桶排序(Bucket Sort)
9. 基数排序(Radix Sort)
10. 希尔排序(Shell Sort)