十大经典排序算法之希尔排序算法
希尔排序
之前我们讲过冒泡排序、选择排序、插入排序，它们的时间复杂度都是
,比较高，在实际的场景用应用也比较少。
今天我们要讲的希尔排序虽然也是插入排序的一种，但是它是插入排序的一个高效变形，脱离了
的时间复杂度深渊。
主要思想
希尔排序的思想简单点说就是有跨度的插入排序，这个跨度会逐渐变小，直到变为 1,变为 1 的时候也就是我们之前讲的简单插入排序了。
规范点的描述就是,选择一组递减的整数作为增量序列，最小的增量必须为 1。
- 先用第一个增量把数组分为若干个子数组，每个子数组中的元素下标距离等于增量；
- 然后对每个子数组进行简单插入排序
- 再使用第二个增量，然后继续同样的操作，直到增量序列里的增量都使用过一次（增量为 1 时，其实就是对整个数组进行简单插入排序）。
可能你有点疑惑为啥刚开始要进行大跨度的插入排序呢？说实话我刚开始的时候也觉得怪怪的，举个极端的例子帮助你理解下。
假定
，对于简单的插入排序，如果最小的元素位于最后面的话，那么它就需要和所有的元素比较移动一遍，才可以到达它指定的位置，但是刚开始进行大跨度插入排序的时候，它就可以少比较几次就可以到达前面了。
这就是希尔排序的思想。
代码实现
#!/usr/bin/python
# -*- coding: utf-8 -*-
from typing import List
import random
def shell_sort_original(array: List[int]) -> None:
# 增量序列的初始值
gap = len(array) // 2
while gap > 0:
# 对于 array 进行分组，默认编号是 0， 1， 2, ...
for i in range(gap):
# 对于每组进行插入排序
for j in range(i+gap, len(array), gap):
temp = array[j]
index = j - gap
while index >= 0:
if array[index] > temp:
array[index+gap] = array[index]
index -= gap
else:
break
array[index+gap] = temp
# 增量序列值减小，变为原来的 1/2
gap //= 2
if __name__ == "__main__":
min_number, max_number = 0, 100
num = 10
array = [random.randint(min_number, max_number) for _ in range(num)]
print(array)
shell_sort_original(array)
print(array)
乍一看，这个程序一共有四层循环，是不是觉得这个程序怎么可能是插入排序的优化算法呢？但是这个确实是按照希尔排序的思想进行写出来的。
确实，这个程序确实是四层循环，但是呢一个程序的时间复杂度不能单单看循环的层数，更应该看的是程序随着输入的执行次数。
希尔排序的写法优化
虽然上面的写法就是完全按照希尔排序的思想来进行实现的，但是呢，写的不够简洁。
下面带你看下一个更常用的写法：
#!/usr/bin/python
# -*- coding: utf-8 -*-
from typing import List
import random
def shell_sort(array: List[int]) -> None:
# 增量序列
gap = len(array) // 2
while gap > 0:
for i in range(gap, len(array)):
temp = array[i]
index = i - gap
while index >= 0:
if array[index] > temp:
array[index + gap] = array[index]
index -= gap
else:
break
array[index+gap] = temp
gap //= 2
if __name__ == "__main__":
min_number, max_number = 0, 100
num = 10
array = [random.randint(min_number, max_number) for _ in range(num)]
print(array)
shell_sort(array)
print(array)
这种实现方法在表面上模糊了对数组分组的概念，而是在进行插入排序的时候通过设置
的变化值为
(之前是 1)，来实现的。
性能分析
希尔排序的时间复杂度不是我们表面认为的那样，一般来说认为希尔排序的时间复杂度是
,这个证明起来比较难。
空间复杂度的话，希尔排序没有使用额外的空间，进行存储，是原地排序算法。
希尔排序算法不是稳定的排序算法。前面我们也提到过，只要涉及到大跨度的排序算法，一般都不是稳定的排序算法。
优化
希尔排序的优化主要是针对增量序列的优化。增量序列如果取得不好，效率比直接插入排序还要低，下面举个例子1：
这个例子就形象说明了这个问题。
于是呢，人们就研究了一些比较好用的增量序列，比如说Hibbard增量序列、Sedgewick增量序列。
Hibbard增量序列
Hibbard增量序列的取法为
Sedgewick增量序列
Sedgewick增量序列的取法为