大家好，我是梁唐。

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

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

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]);
        }
    }
}

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

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

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

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

組內(nèi)進(jìn)行排序之后，我們接著將跨度縮小一半，從5變成2，接著重復(fù)上述邏輯，得到：

最后，跨度設(shè)為1，總體進(jìn)行插入排序，得到結(jié)果。由于我們之前已經(jīng)調(diào)整了幾次元素的位置，最后一次插入排序的交換元素的次數(shù)大大減小。

我們來嘗試著寫出代碼：

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;
    }
}

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

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

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