大家好，我是梁唐。

今天選中的算法是希爾排序，它本質上是插入排序的優化。是簡單的插入排序改進之后的版本，也成為縮小增量排序。也是第一個突破復雜度的算法。

為了更好地理解它和插入排序之間的差異，我們再來復習一下插入排序：

void insert_sort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 1; i < n; i++) {
        for (int j = i; j >-1 && nums[j] < nums[j-1] ; j--) {
            swap(nums[j], nums[j-1]);
        }
    }
}

我們每次拿到一個新的數nums[i]時，通過一重循環，將它往前移動到插入的位置。我們分析一下代碼會發現一個問題，如果我們在數組的后段遇到了一個較小的元素，那么我們需要經過多次的交換才能讓它回到正確的位置上。

比如最后的0，需要跨過整個數組才能到達下標0，這樣的元素多了，就會非常影響算法的性能。希爾排序正是針對這個問題的優化，有沒有辦法能夠讓元素能夠盡量快地移動，從而降低運行的復雜度呢?

希爾排序的做法是先將元素進行分組，每次先在組內進行排序，盡量讓元素可以在早期盡量多地移動。

比如還是上面的元素，我們第一次選擇分組的跨度是5，一開始的跨度是數組長度的一半。我們可以參考上圖，相同顏色的元素為一組。以其中的8和3為例，我們在組內進行插入排序之后，會使得3和8調換位置。對于元素3而言，它通過一次交換就移動到了數組的最前面。顯然比依次移動要快得多。

組內進行排序之后，我們接著將跨度縮小一半，從5變成2，接著重復上述邏輯，得到：

最后，跨度設為1，總體進行插入排序，得到結果。由于我們之前已經調整了幾次元素的位置，最后一次插入排序的交換元素的次數大大減小。

我們來嘗試著寫出代碼：

void shell_sort(vector<int>& nums) {
    int n = nums.size();
    int h = n / 2;
    while (h > 0) {
        for (int i = h; i < n; i++) {
            for (int j = i; j >= h && nums[j] < nums[j-h]; j-=h) swap(nums[j], nums[j-h]);
        }
        h >>= 1;
    }
}

希爾排序的原理看起來復雜，但代碼實現卻很簡單。不過這段代碼雖然短，但想要寫好可不容易，值得大家好好揣摩。

最后，聊一下關于算法的復雜度，關于希爾排序的復雜度的證明過程非常的復雜，因此書中也沒有詳細闡述，感興趣的同學可以去搜索引擎去搜索一下相關內容。我保證它肯定比算法本身要難懂得多，大致上我們可以把希爾排序的復雜度理解成左右。

我們通過一個小小的優化，就減小了排序問題的復雜度，不得不說還是很神奇的。排序算法雖然看起來簡單，但當中的內核以及原理其實一點都不簡單，之后還有更多的內容在等待著大家，讓我們一起期待吧。