IT江湖
通过直接插入排序的修炼，我们知道直接插入排序是一种性能比较低的初级算法，对修炼者提升不是不大， 但是有一点优势那就是对于小型数组或者部分有序的数组非常高效，希尔排序就是基于这一点优势对直接插入排序进行了改良。换句话说直接插入排序低效的原因在于无序，无序的程度越高越低效。例如：最小的元素初始位置在数组的另一端，此元素要想到达正确位置，是需要一个一个位置前移，最终需要N-1次移动。如何改变这种状态正是希尔排序的突破口。
希尔排序的思想是把数组下标按照一定的增量h分组，然后对每组进行直接插入排序。在进行排序时，如果h很大，我们就能将元素移动到很远的地方，为实现更小的h有序创造方便。然后增量h逐渐减小（每个分组的元素量增多），直到h为1整个数组划分为一组，排序结束。
也许一张更直观的图比上千句话效果都好
与插入排序不同，希尔排序可以适用于大型数组，它对任意排序的数组表现良好，虽然不是最好。实验证明，希尔排序比我们上两章学习的选择排序和插入排序要快的多，并且数组越大，优势越大。目前最重要的结论是：希尔排序的运行时间达不到平方级别。
对于中等大小的数组希尔排序的时间是在可接受范围之内的，因为它的代码量很小，而且需要的额外空间很小，几乎可以忽略。对于其他更高效的其他算法，可能比希尔排序更高效，但是代码也更复杂，性能上比希尔排序也高不了几倍，所以在很多情况下希尔排序成为首选的算法。
1. 直接插入排序是稳定的，希尔排序呢？
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序排序是不稳定的。
c#武器版本
1static void Main(string[] args)
2 {
3
4 List<int> data = new List<int>() ;
5
6 for (int i = 0; i < 11; i++)
7 {
8 data.Add(new Random(Guid.NewGuid().GetHashCode()).Next(1, 100));
9 }
10 //打印原始数组值
11 Console.WriteLine($"原始数据： {string.Join(",", data)}");
12 int n = data.Count;
13 int h = 1;
14 //计算初始化增量，网络提供，据说比较好的递增因子
15 while (h < n / 3)
16 {
17 h = 3 * h + 1;
18 }
19
20 Console.WriteLine($"初始化增量：{h}");
21
22 while (h >= 1)
23 {
24 for (int i = h; i < n; i++)
25 {
26 for (int j = i; j >=h&&data[j]<data[j-h]; j-=h)
27 {
28 //异或法 交换两个变量，不用临时变量
29 data[j] = data[j] ^ data[j - 1];
30 data[j - 1] = data[j] ^ data[j - 1];
31 data[j] = data[j] ^ data[j - 1];
32 }
33 }
34 h = h / 3;
35 }
36
37
38 //打印排序后的数组
39 Console.WriteLine($"排序数据： {string.Join(",", data)}"); Console.Read();
40 }
运行结果：
golang武器版本原始数据： 47,50,32,42,44,79,10,16,51,74,52
初始化增量：4
排序数据： 10,16,32,42,44,47,50,51,52,74,79
1package main
2import (
3 "fmt"
4 "math/rand"
5)
6
7func main() {
8 var data []int
9 for i := 0; i < 11; i++ {
10 data = append(data, rand.Intn(100))
11 }
12 fmt.Println(data)
13 var n = len(data)
14 var h = 1
15 for h < n/3 {
16 h = 3*h + 1
17 }
18 fmt.Println(h)
19 for h >= 1 {
20 for i := h; i < n; i++ {
21 for j := i; j >= h && data[j] < data[j-h]; j -= h {
22 data[j], data[j-h] = data[j-h], data[j]
23 }
24 }
25 h = h / 3
26 }
27 fmt.Println(data)
28}
运行结果：
[81 87 47 59 81 18 25 40 56 0 94]
4
[0 18 25 40 47 56 59 81 81 87 94]
