自馮諾依曼開啟大計算機時代以來，經過近一個世紀的蓬勃發展，已然成為一個人才衆多的群體：IT江湖
依附市場規律，江湖上悄然興起數十宗門，其中以AI，大資料近期最為熱門。每個宗門人才濟濟，搶奪人才大戰早已在阿裡，騰訊，百度等數百個國度白熱化。
IT江湖人士憑借JAVA，Python等武器，在精通各路内功心法的基礎上在各個國度揚名立萬，修仙成佛者衆多，為後人樹下追寵之榜樣。
内功心法衆多，其中以算法最為精妙，是修仙德道必經之路。
雖然江湖上算法内功繁多，但是好的算法小編認為必須符合以下幾個條件，方能真正提高習練者實力：
時間複雜度（運作時間）在算法時間複雜度次元，我們主要對比較和交換的次數做對比，其他不交換元素的算法，主要會以通路數組的次數的次元做對比。。
其實有很多修煉者對于算法的時間複雜度有點模糊，分不清什麼所謂的 O(n),O(nlogn),O(logn)...等，也許下圖對一些人有一些更直覺的認識。
排序算法的額外記憶體開銷和運作時間同等重要。 就算一個算法時間複雜度比較優秀，空間複雜度非常差，使用的額外記憶體非常大，菜菜認為它也算不上一個優秀的算法。
結果的正确性這個名額是菜菜自己加上的，我始終認為一個優秀的算法最終得到的結果必須是正确的。就算一個算法擁有非常優秀的時間和空間複雜度，但是結果不正确，導緻修煉者經脈逆轉，走火入魔，又有什麼意義呢？
算法雖然精妙，但需循序漸進修煉，并且需要一定的數學内功基礎方可徹底領悟。今日習練算法第三章：排序之希爾排序。
氣運丹田 開啟修煉之路心法簡介
上一篇我們修煉了插入排序，希爾排序（又名Shell's Sort）本質上屬于插入排序，是插入排序的一種更高效更新版本，也稱為**縮小增量排序**。同時希爾排序在時間複雜度上也是突破O(n²）的第一批算法之一。你說厲不厲害？~~
心法基本思想
通過直接插入排序的修煉，我們知道直接插入排序是一種性能比較低的初級算法，對修煉者提升不是不大， 但是有一點優勢那就是對于小型數組或者部分有序的數組非常高效，希爾排序就是基于這一點優勢對直接插入排序進行了改良。換句話說直接插入排序低效的原因在于無序，無序的程度越高越低效。例如：最小的元素初始位置在數組的另一端，此元素要想到達正确位置，是需要一個一個位置前移，最終需要N-1次移動。如何改變這種狀态正是希爾排序的突破口。
希爾排序的思想是把數組下标按照一定的增量h分組，然後對每組進行直接插入排序。在進行排序時，如果h很大，我們就能将元素移動到很遠的地方，為實作更小的h有序創造友善。然後增量h逐漸減小（每個分組的元素量增多），直到h為1整個數組劃分為一組，排序結束。
也許一張更直覺的圖比上千句話效果都好
時間複雜度
最壞時間複雜度依然為O(n²)，一些經過優化的增量序列如Hibbard經過複雜證明可使得最壞時間複雜度為O(n^3/2)，最好情況下為O(n)屬于線性複雜度。
空間複雜度
優于希爾排序本質上屬于插入排序更新版，是以空間上和直接插入排序一緻為O(1)，在常數級别。
性能和特點希爾排序之是以高效是因為它權衡了子數組的規模和有序性。排序之初各個子數組都很短，這種情況很适合插入排序.
對于增量h的選擇對希爾排序非常重要，直接影響其性能。其實除了h的選擇之外，h之間的數學性質也影響希爾排序的性能，比如它們的公因子等。很多論文研究了各種不同的遞增序列，但都無法證明某個序列是最好的。對于某些基礎遞增的序列其實在性能上和某些複雜的序列接近，是以很多情況下我們沒有必要花大力氣在複雜序列上的研究上。
适用場景與插入排序不同，希爾排序可以适用于大型數組，它對任意排序的數組表現良好，雖然不是最好。實驗證明，希爾排序比我們上兩章學習的選擇排序和插入排序要快的多，并且數組越大，優勢越大。目前最重要的結論是：希爾排序的運作時間達不到平方級别。
對于中等大小的數組希爾排序的時間是在可接受範圍之内的，因為它的代碼量很小，而且需要的額外空間很小，幾乎可以忽略。對于其他更高效的其他算法，可能比希爾排序更高效，但是代碼也更複雜，性能上比希爾排序也高不了幾倍，是以在很多情況下希爾排序成為首選的算法。
其他1. 直接插入排序是穩定的，希爾排序呢？
由于多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最後其穩定性就會被打亂，是以希爾排序排序是不穩定的。
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]
原文釋出時間為：2018-11-29
本文作者：大菜
本文來自雲栖社群合作夥伴“
Golang語言社群”，了解相關資訊可以關注“
”。