希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL. Shell于1959年提出而得名。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序﹔随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
1.1 希尔排序过程希尔排序的基本思想是:将数组列在一个表中并对列分别进行插入排序，重复这试程，不过每次用更长的列(步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。
例如，假设有这样一组数 [13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样(竖着的元素是步长组成):
13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10
这里可以看成每5个数取一个放在第一列中。但现在有一个更加便捷的方法，就是每gap（步长）个数就换行。
- [13 14 94 33 82]这是gap个数，换行（将它们放在第一行）
- [25 59 94 65 23]这是gap个数，换行（将它们放在第二行）
- …以此类推
然后我们对每列进行排序：
10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45
将上述四行数字，依次接在一起时我们就可以得到 [10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45]。这时，数字10已经移至正确的位置了。
然后我们再以3为步长进行分组和排序。
10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45
排序之后变为：
10 14 13 25 23 33 27 25 59 39 65 73 45 94 82 94
最后以步长为1进行排序（就是简单的插入排序了）
1.2 希尔排序的动画演示 1.3 希尔排序的时间复杂度- 最优时间复杂度：根据步长和序列的不同而不同（步长gap的不同会影响这个算法的时间复杂度，如果gap取的非常合适，那么该排序算法的时间复杂度会非常低）
- 最坏时间复杂度： O ( n 2 ) O(n^2) O(n2) -> 直接取gap=1就是最坏的情况
- 稳定性：不稳定 -> 因为我们把序列分成几部分去对待了（分治的思想），所以数据并不稳定。
我们可以看一下下面这个表，就知道了，其实希尔排序的时间复杂度还好。
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O ( n 2 ) O(n^2) O(n2) | O ( n ) O(n) O(n) | O ( n 2 ) O(n^2) O(n2) | O ( 1 ) O(1) O(1) | 稳定 |
| 选择排序 | O ( n 2 ) O(n^2) O(n2) | O ( n 2 ) O(n^2) O(n2) | O ( n 2 ) O(n^2) O(n2) | O ( 1 ) O(1) O(1) | 不稳定 |
| 插入排序 | O ( n 2 ) O(n^2) O(n2) | O ( n ) O(n) O(n) | O ( n 2 ) O(n^2) O(n2) | O(1) | 稳定 |
| 希尔排序 | O ( n log n ) O(nlog^n) O(nlogn) ~ O ( n 2 ) O(n^2) O(n2) | O ( n 1.3 ) O(n^{1.3}) O(n1.3) | O ( n 2 ) O(n^2) O(n2) | O ( 1 ) O(1) O(1) | 不稳定 |
| 堆排序 | O ( n log n ) O(nlog^n) O(nlogn) | O ( n log n ) O(nlog^n) O(nlogn) | O ( n log n ) O(nlog^n) O(nlogn) | O ( 1 ) O(1) O(1) | 不稳定 |
| 归并排序 | O ( n log n ) O(nlog^n) O(nlogn) | O ( n log n ) O(nlog^n) O(nlogn) | O ( n log n ) O(nlog^n) O(nlogn) | O ( n ) O(n) O(n) | 稳定 |
| 快速排序 | O ( n log n ) O(nlog^n) O(nlogn) | O ( n log n ) O(nlog^n) O(nlogn) | O ( n 2 ) O(n^2) O(n2) | O ( log n ) O(log^n) O(logn) ~ O ( n ) O(n) O(n) | 不稳定 |
从表中可以看到，希尔排序其实和插入排序是差不多的，在最好的情况下，插入排序是 O ( n ) O(n) O(n)，而希尔排序是 O ( n 1.3 ) O(n^{1.3}) O(n1.3)，虽然比插入要弱一些，但是希尔排序的平均情况是要比插入排序要好的。二者在最坏情况下所耗费的资源是一样的，这其实就说明了，在不保证数据稳定性的前提下，希尔排序一般是要比插入排序要好一些的。
1.4 希尔排序的算法实现# coding: utf-8
def shell_sort(alist):
"""希尔排序"""
n = len(alist)
gap = n // 2 # 这里我们就简单粗暴的二分
i = 1
while gap > 0: # 当gap变为1时，希尔排序算法结束(这里必须是gap==1才能结束，不然不能保证排序算法的正确性)
# 当gap=1时，就是一个普通的排序方法。
"""
希尔排序中的插入算法与普通的插入算法的区别就是步长gap（普通的步长是1），其他都是一样的，
"""
for j in range(gap, n): # 从gap右边开始，一个元素一个元素的开始插入排序，但这里的插入不是看元素前面的元素，
# 而是前面第gap个元素
# j = [gap, gap+1, gap+2, gap+3, ..., n-1]
i = j
while i > 0: # 只要该元素还能比较，那么就让它一直比较 -> 插入算法
if alist[i] < alist[i - gap]: # 比较的相邻元素不再是1而是步长gap
alist[i], alist[i - gap] = alist[i - gap], alist[i]
i -= gap # 接着往前比较，但这里的移动是gap不能是1
else: # 说明该元素比前面的所有元素都大，那么就不用挪动了，所以break就可以
break
# 缩短gap步长，继续插入算法（这里我们就简单粗暴的二分）
gap //= 2 # 让gap继续二分
if __name__ == "__main__":
ls = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(ls)
shell_sort(ls)
print(ls)
希尔排序的gap如何取其实是非常重要的，像上面的代码实现中，我们就只是简单粗暴地将gap二分，但实际上对于不同的序列应该有最优的gap取值方式。但如何取gap是属于数学方面的知识了，这里我们就不涉及了。
2. 归并算法 (Merge Sort)我们主要是要知道希尔排序的思想。
归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。
将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，被取了数的指针就相应地往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
对于一个数组: [54, 26, 93, 17, 77, 31, 44, 55]，归并排序需要先对数组进行二分，无限二分直到每一个序列只有一个元素为止。
[54, 26, 93, 17, 77, 31, 44, 55]
↓
[54, 26, 93, 17] [77, 31, 44, 55]
↓
[54, 26] [93, 17] [77, 31] [44, 55]
↓
[54] [26] [93] [17] [77] [31] [44] [55]
拆成[54] [26] [93] [17] [77] [31] [44] [55]这样的情况后，每两个元素进行合并（Merging），合并的时候采用 小的数在前，大的数在后：
[54] [26] [93] [17] [77] [31] [44] [55]
↓ ↓ ↓ ↓
[26, 54] [17, 93] [31, 77] [44, 55]
以上就是第一次合并的过程，那么很容易想到我们需要继续往上合，一直合到原始数组大小即可：
[26, 54] [17, 93] [31, 77] [44, 55]
↓ ↓ ↓ ↓
[17, 26, 54, 93] [31, 44, 77, 55]
因为涉及到了两个不同的数组，因此在进行merging时，需要使用两个cursor来引导的进行，如下图所示：
经过如上图所示的计算，我们得到第二次merge后的结果：
[17, 26, 54, 93] [31, 44, 77, 55]
现在还有两个序列，所以我们还需要继续merge：
以上就是归并算法的思想：
- 先将这个序列进行二分拆，一直拆到每个序列只有一个元素的时候为止：n -> … -> 8 -> 4 -> 2 -> 1
- 开始两两合并: 1 -> 2 -> 4 -> 8 -> … -> n
思考一个问题：上面我们讲的例子是偶数个，那如果是奇数个呢？
看下图：
所以说其实是一样的。
2.2 归并排序代码实现对于归并排序来说，顾名思义，我们仍然是需要使用到递归这种方法的。
# coding: utf-8
def merge_sort(alist):
"""归并排序"""
n = len(alist)
if n <= 1: # 每个序列的长度只有一个，那个拆分的递归可以结束了，返回拆分后的结果
return alist
mid = n // 2 # 序列中间元素的idx
# left, right为采用归并排序后形成的有序新列表
left_ls = merge_sort(alist[:mid]) # 调用自身，继续往下拆
right_ls = merge_sort(alist[mid:])
# 将两个有序的子序列（left部分和right部分）进行合并，合并后为一个新的整体
# merge(left_ls, right_ls)
left_cursor, right_cursor = 0, 0 # 两个指针最初都指向各自序列的开头
result = [] # 新建一个ls，用来存在合并后的结果
while left_cursor < len(left_ls) and right_cursor < len(right_ls):
if left_ls[left_cursor] <= right_ls[right_cursor]: # 对两个指针的值进行比较（这里一定要是 <= 不然该算法为不稳定排序算法）
result.append(left_ls[left_cursor]) # 小的值取出来
left_cursor += 1 # 移动指针
else:
result.append(right_ls[right_cursor])
right_cursor += 1 # 移动指针
# 退出循环后，将两个数组后面的数追加到结果中
result += left_ls[left_cursor:] # 不会出现越界异常，超出index后返回的是空列表
result += right_ls[right_cursor:]
return result
if __name__ == "__main__":
ls = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(ls)
sorted_ls = merge_sort(ls) # merge sort需要有一个返回值接收
print(ls)
print(sorted_ls)
2.3 归并排序简洁代码
from heapq import merge
def merge_sort(alist):
if len(alist) <= 1:
return alist
# 二分分解
num = len(alist) // 2
left_ls = merge_sort(alist[:num])
right_ls = merge_sort(alist[num:])
# 合并
return merge(left_ls, right_ls)
def merge(left_ls, right_ls):
"""合并操作，将两个有序数组left_ls和right_ls合并为一个大的有序数组"""
# left与right的下标
l, r = 0, 0
result = []
while l < len(left_ls) and r < len(right_ls):
if left_ls[l] <= right_ls[r]: # 这里一定要是 <= 不然该算法为不稳定排序算法
result.append(left_ls[l])
l += 1
else:
result.append(right_ls[r])
r += 1
result += left_ls[l:]
result += right_ls[r:]
return result
if __name__ == "__main__":
ls = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(ls)
sorted_ls = merge_sort(ls) # merge sort需要有一个返回值接收
print(ls)
print(sorted_ls)
2.4 归并排序算法分析
我们来具体分析一下上面的代码：
2.5 归并排序的时间复杂度因为代码中涉及到了递归，其时间复杂度就不那么容易看出来，因此我们需要对整个过程进行分析。
从图中可以看到，归并排序一上来需要对整个序列进行拆分，而且拆分的这个过程是没有涉及到循环，所以将其复杂度认为是 O ( 1 ) O(1) O(1)，即拆分和 n n n无关。
在合并的时候是两两合并，虽然是在不同的嵌入函数中执行，但是没有被循环包着，所以这个合并的操作可以看成是顺序执行的，即不同循环嵌套（递归）合并的时间复杂度是相加的关系。
在合并中，主要是时间复杂度是 比较，那么我们需要考虑横向比较的时候，时间复杂度是多少 -> 稍加思考我们就可以知道，每一次合并的时间复杂度为 O ( n ) O(n) O(n)。
为了求总的时间复杂度，所以我们需要知道怎么合并了多少次，将所有的加起来就是总的时间复杂度，其实就是 O ( t × n ) O(t times n) O(t×n)
因为分的时候是二分，所以和快排类似，是一个 l o g 2 log_2 log2的形式，即 2 t = n 2^t = n 2t=n -> 所以我们就可以求出二分的次数，也就是merge的次数： t = log 2 n t = log_2^n t=log2n，所以归并排序总的时间复杂度为： O ( n ) = n log 2 n O(n) = nlog_2^n O(n)=nlog2n。
而且我们思考一下，对于归并算法而言，它的最好和最优的时间复杂度该怎么求？
其实我们从程序中可以看到，归并是没有超参数的，二分的次数是和数列的长度 n n n相关，所以它的最好和最坏时间复杂度是一样的。即便对于一个已经排好的序列，它也需要二分，再merge，所以它的最好、最坏复杂度是一样的。
现在我们需要考虑一下归并算法的稳定性，看看它在排序的过程中是否会破坏原有数据的顺序。
其实这里主要思考的是merge过程中是否会破坏元素的顺序，对于拆分而言，因为使用的是二分法，所以肯定不会破坏元素原有的顺序。
这里主要考虑的是：在合并的过程中是否可能有相同的元素，但是在merge的过程中会打乱二者的顺序。
我们看一下下面这张图：
可以看到，两个54在使用归并排序后，二者的顺序并没有被打乱，因此归并排序（merge sort）是稳定的。
综上所述：
- 归并排序的最优时间复杂度： n log 2 n nlog_2^n nlog2n
- 归并排序的最坏时间复杂度： n log 2 n nlog_2^n nlog2n
- 稳定性：稳定
综上所述，归并排序的最坏时间复杂度为 n log 2 n nlog_2^n nlog2n，是目前学习到最好的最坏时间复杂度的算法。但是归并排序有一个问题，因为本身的原理，归并排序后的序列是一个新的序列，并不是在原有list上直接进行改动的。
因此归并排序算法在时间复杂度上是小的，但是在空间上需要产生一块与原有序列同样大小的空间来对排序后的序列进行保存。别的排序算法是不用这样的，不涉及到额外的空间开销。
3. 常见排序算法效率对比| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O ( n 2 ) O(n^2) O(n2) | O ( n ) O(n) O(n) | O ( n 2 ) O(n^2) O(n2) | O ( 1 ) O(1) O(1) | 稳定 |
| 选择排序 | O ( n 2 ) O(n^2) O(n2) | O ( n 2 ) O(n^2) O(n2) | O ( n 2 ) O(n^2) O(n2) | O ( 1 ) O(1) O(1) | 不稳定 |
| 插入排序 | O ( n 2 ) O(n^2) O(n2) | O ( n ) O(n) O(n) | O ( n 2 ) O(n^2) O(n2) | O(1) | 稳定 |
| 希尔排序 | O ( n log n ) O(nlog^n) O(nlogn) ~ O ( n 2 ) O(n^2) O(n2) | O ( n 1.3 ) O(n^{1.3}) O(n1.3) | O ( n 2 ) O(n^2) O(n2) | O ( 1 ) O(1) O(1) | 不稳定 |
| 堆排序 | O ( n log n ) O(nlog^n) O(nlogn) | O ( n log n ) O(nlog^n) O(nlogn) | O ( n log n ) O(nlog^n) O(nlogn) | O ( 1 ) O(1) O(1) | 不稳定 |
| 归并排序 | O ( n log n ) O(nlog^n) O(nlogn) | O ( n log n ) O(nlog^n) O(nlogn) | O ( n log n ) O(nlog^n) O(nlogn) | O ( n ) O(n) O(n) | 稳定 |
| 快速排序 | O ( n log n ) O(nlog^n) O(nlogn) | O ( n log n ) O(nlog^n) O(nlogn) | O ( n 2 ) O(n^2) O(n2) | O ( log n ) O(log^n) O(logn) ~ O ( n ) O(n) O(n) | 不稳定 |
其中 快排是必须要掌握的一种排序方法（归并用的比较少，但是快排用的是最多的）。虽然快排的最坏时间复杂度是 O ( n 2 ) O(n^2) O(n2),但它更接近于 n log 2 n nlog_2^n nlog2n，平均时间复杂度也可以看出来，快排是更加接近 n log 2 n nlog_2^n nlog2n，且快排是不需要额外的空间。因此在实际项目中，快排用的是比较多的。
虽然快排是不稳定的排序算法，但是在不保序的情况下，快排是用的最多的。
g^n) ∣ | ∣O(1) ∣ 不 稳 定 ∣ ∣ 归 并 排 序 ∣ |不稳定| |归并排序| ∣不稳定∣∣归并排序∣O(nlogn)$|$O(nlogn) ∣ | ∣O(nlog^n) ∣ | ∣O(n) ∣ 稳 定 ∣ ∣ 快 速 排 序 ∣ |稳定| |快速排序| ∣稳定∣∣快速排序∣O(nlogn)$|$O(nlogn) ∣ | ∣O(n2)$|$O(logn)$ ~ O ( n ) O(n) O(n)|不稳定|
其中 快排是必须要掌握的一种排序方法（归并用的比较少，但是快排用的是最多的）。虽然快排的最坏时间复杂度是 O ( n 2 ) O(n^2) O(n2),但它更接近于 n log 2 n nlog_2^n nlog2n，平均时间复杂度也可以看出来，快排是更加接近 n log 2 n nlog_2^n nlog2n，且快排是不需要额外的空间。因此在实际项目中，快排用的是比较多的。
虽然快排是不稳定的排序算法，但是在不保序的情况下，快排是用的最多的。
保序的这种场景其实并不多见。
