希尔排序
# 介绍
希尔排序是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本，希尔排序是非稳定排序算法，该方法因“D.L.Shell”于 1959 年提出而得名。
插入排序在小规模数据或者基本有序时非常高效，数据有序程度越高，越高效。而希尔排序就是对它的一种改良，使得它对较大规模并且无序的数据也非常有效率。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
# 思路
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
# 图解
1.排序下面序列（原始数组，元素颜色相同的为一组）
2.初始增量 gap = length / 2 = 5，也就是说整个数组分成 5 组:[8, 3] [9, 5] [1, 4] [7, 6] [2, 0]
3.对这 5 组进行插入排序，结果如下，之后缩小增量 gap = 5 / 2 = 2，数组分成了 2 组：[3, 1, 0, 9, 7] [5, 6, 8, 4, 2]
4.再对上面两个数组进行插入排序，结果如下，再次缩小增量 gap = 2 / 2 = 1，整个数组只有一组数据了[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
5.之后只需对这个数组进行微调，无需进行大量的移动操作，即可完成整个数组的排序
# 代码实现
var tmp = [4,32,5,6,8,10,31,7]
/// 希尔排序
func insertSort(_ list: inout[Int], start: Int, gap: Int) {
for i in stride(from: (start + gap), to: list.count, by: gap) {
let currentValue = list[i]
var pos = i
while pos > gap && list[pos - gap] > currentValue {
list[pos] = list[pos - gap]
pos -= gap
}
list[pos] = currentValue
}
}
func shellSort(_ list: inout [Int]) {
var sublistCount = list.count / 2
while sublistCount > 0 {
for pos in 0..<sublistCount {
insertSort(&list, start: pos, gap: sublistCount)
}
sublistCount = sublistCount / 2
}
}
shellSort(&tmp)
# 性能
在大多数情况下，希尔排序的性能为 O(n^2)，如果幸运，则为 O(nlogn)。 该算法是不稳定的排序，它可能会改变具有相等值的元素的相对顺序。
步长的选择是希尔排序的重要部分。只要最终步长为 1 任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为 1 进行排序。当步长为 1 时，算法变为普通插入排序，这就保证了数据一定会被排序。