自馮諾依曼開啟大計算機時代以來，經(jīng)過近一個世紀(jì)的蓬勃發(fā)展，已然成為一個人才眾多的群體：IT江湖。 依附市場規(guī)律，江湖上悄然興起數(shù)十宗門，其中以AI，大數(shù)據(jù)近期最為熱門。 每個宗門人才濟濟，搶奪人才大戰(zhàn)早已在阿里，騰訊，百度等數(shù)百個國度白熱化。 IT江湖人士憑借JAVA，Python等武器，在精通各路內(nèi)功心法的基礎(chǔ)上在各個國度揚名立萬，修仙成佛者眾多，為后人樹下追寵之榜樣。

內(nèi)功心法眾多，其中以算法最為精妙，是修仙德道必經(jīng)之路。

雖然江湖上算法內(nèi)功繁多，但是好的算法小編認(rèn)為必須符合以下幾個條件，方能真正提高習(xí)練者實力。

• 時間復(fù)雜度（運行時間）

在算法時間復(fù)雜度維度，我們主要對比較和交換的次數(shù)做對比，其他不交換元素的算法，主要會以訪問數(shù)組的次數(shù)的維度做對比。

其實有很多修煉者對于算法的時間復(fù)雜度有點模糊，分不清什么所謂的 O(n),O(nlogn),O(logn)...等，也許下圖對一些人有一些更直觀的認(rèn)識。

<figcaption style="display: block; text-align: center; font-size: 1rem; line-height: 1.6; color: rgb(144, 144, 144); margin-top: 2px;"></figcaption>

• 空間復(fù)雜度（額外的內(nèi)存使用）

排序算法的額外內(nèi)存開銷和運行時間同等重要。 就算一個算法時間復(fù)雜度比較優(yōu)秀，空間復(fù)雜度非常差，使用的額外內(nèi)存非常大，菜菜認(rèn)為它也算不上一個優(yōu)秀的算法。

• 結(jié)果的正確性

這個指標(biāo)是菜菜自己加上的，我始終認(rèn)為一個優(yōu)秀的算法最終得到的結(jié)果必須是正確的。就算一個算法擁有非常優(yōu)秀的時間和空間復(fù)雜度，但是結(jié)果不正確，導(dǎo)致修煉者經(jīng)脈逆轉(zhuǎn)，走火入魔，又有什么意義呢？

原理

在上一篇我們修煉了插入排序，希爾排序（又名Shell's Sort）本質(zhì)上屬于插入排序，是插入排序的一種更高效升級版本，也稱為縮小增量排序。同時希爾排序在時間復(fù)雜度上也是突破O(n2）的第一批算法之一。你說厲不厲害？~~

基本思想

通過直接插入排序的修煉，我們知道直接插入排序是一種性能比較低的初級算法，對修煉者提升不是不大， 但是有一點優(yōu)勢那就是對于小型數(shù)組或者部分有序的數(shù)組非常高效，希爾排序就是基于這一點優(yōu)勢對直接插入排序進行了改良。換句話說直接插入排序低效的原因在于無序，無序的程度越高越低效。例如：最小的元素初始位置在數(shù)組的另一端，此元素要想到達(dá)正確位置，是需要一個一個位置前移，最終需要N-1次移動。如何改變這種狀態(tài)正是希爾排序的突破口。 希爾排序的思想是把數(shù)組下標(biāo)按照一定的增量h分組，然后對每組進行直接插入排序。在進行排序時，如果h很大，我們就能將元素移動到很遠(yuǎn)的地方，為實現(xiàn)更小的h有序創(chuàng)造方便。然后增量h逐漸減?。總€分組的元素量增多），直到h為1整個數(shù)組劃分為一組，排序結(jié)束。

也許一張更直觀的圖比上千句話效果都好

<figcaption style="display: block; text-align: center; font-size: 1rem; line-height: 1.6; color: rgb(144, 144, 144); margin-top: 2px;"></figcaption>

復(fù)雜度

• 時間復(fù)雜度

最壞時間復(fù)雜度依然為O(n2)，一些經(jīng)過優(yōu)化的增量序列如Hibbard經(jīng)過復(fù)雜證明可使得最壞時間復(fù)雜度為O(n^3/2)，最好情況下為O(n)屬于線性復(fù)雜度。

• 空間復(fù)雜度

優(yōu)于希爾排序本質(zhì)上屬于插入排序升級版，所以空間上和直接插入排序一致為O(1)，在常數(shù)級別。

性能和特點

• 希爾排序之所以高效是因為它權(quán)衡了子數(shù)組的規(guī)模和有序性。排序之初各個子數(shù)組都很短，這種情況很適合插入排序。
• 對于增量h的選擇對希爾排序非常重要，直接影響其性能。其實除了h的選擇之外，h之間的數(shù)學(xué)性質(zhì)也影響希爾排序的性能，比如它們的公因子等。很多論文研究了各種不同的遞增序列，但都無法證明某個序列是最好的。對于某些基礎(chǔ)遞增的序列其實在性能上和某些復(fù)雜的序列接近，所以很多情況下我們沒有必要花大力氣在復(fù)雜序列上的研究上。

適用場景

與插入排序不同，希爾排序可以適用于大型數(shù)組，它對任意排序的數(shù)組表現(xiàn)良好，雖然不是最好。實驗證明，希爾排序比我們上兩章學(xué)習(xí)的選擇排序和插入排序要快的多，并且數(shù)組越大，優(yōu)勢越大。 目前最重要的結(jié)論是：希爾排序的運行時間達(dá)不到平方級別。 對于中等大小的數(shù)組希爾排序的時間是在可接受范圍之內(nèi)的，因為它的代碼量很小，而且需要的額外空間很小，幾乎可以忽略。對于其他更高效的其他算法，可能比希爾排序更高效，但是代碼也更復(fù)雜，性能上比希爾排序也高不了幾倍，所以在很多情況下希爾排序成為首選的算法。

歡迎工作一到五年的Java工程師朋友們加入Java高并發(fā)： 957734884，

群內(nèi)提供免費的Java架構(gòu)學(xué)習(xí)資料（里面有高可用、高并發(fā)、高性能及分布式、Jvm性能調(diào)優(yōu)、Spring源碼，MyBatis，Netty,Redis,Kafka,Mysql,Zookeeper,Tomcat,Docker,Dubbo,Nginx等多個知識點的架構(gòu)資料）

合理利用自己每一分每一秒的時間來學(xué)習(xí)提升自己，不要再用"沒有時間“來掩飾自己思想上的懶惰！趁年輕，使勁拼，給未來的自己一個交代！

其他

直接插入排序是穩(wěn)定的，希爾排序呢？

由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩(wěn)定性就會被打亂，所以希爾排序排序是不穩(wěn)定的。

試煉一發(fā)吧

c# 武器版

        static void Main(string[] args)
        {
            List<int> data = new List<int>() ;
            for (int i = 0; i < 11; i++)
            {

                data.Add(new Random(Guid.NewGuid().GetHashCode()).Next(1, 100));
            }
            //打印原始數(shù)組值
            Console.WriteLine($"原始數(shù)據(jù)： {string.Join(",", data)}");
            int n = data.Count;
            int h = 1;
            //計算初始化增量，網(wǎng)絡(luò)提供，據(jù)說比較好的遞增因子
            while (h < n / 3)
            {
                h = 3 * h + 1;
            }
            Console.WriteLine($"初始化增量：{h}");
            while (h >= 1)
            {
                for (int i = h; i < n; i++)
                {
                    for (int j = i; j >=h&&data[j]<data[j-h]; j-=h)
                    {
                        //異或法 交換兩個變量，不用臨時變量
                        data[j] = data[j] ^ data[j - 1];
                        data[j - 1] = data[j] ^ data[j - 1];
                        data[j] = data[j] ^ data[j - 1];
                    }
                }
                h = h / 3;
            }

            //打印排序后的數(shù)組
            Console.WriteLine($"排序數(shù)據(jù)： {string.Join(",", data)}");
            Console.Read();
        }
復(fù)制代碼

運行結(jié)果：

原始數(shù)據(jù)： 47,50,32,42,44,79,10,16,51,74,52

初始化增量：4

排序數(shù)據(jù)： 10,16,32,42,44,47,50,51,52,74,79

Golang 武器版

package main

import (
    "fmt"
    "math/rand"
)

func main() {
    var data []int
    for i := 0; i < 11; i++ {
        data = append(data, rand.Intn(100))
    }
    fmt.Println(data)
    var n = len(data)
    var h = 1
    for h < n/3 {
        h = 3*h + 1
    }
    fmt.Println(h)
    for h >= 1 {
        for i := h; i < n; i++ {
            for j := i; j >= h && data[j] < data[j-h]; j -= h {
                data[j], data[j-h] = data[j-h], data[j]
            }
        }
        h = h / 3
    }
    fmt.Println(data)
}
復(fù)制代碼

運行結(jié)果：

 [81 87 47 59 81 18 25 40 56 0 94]

 4

 [0 18 25 40 47 56 59 81 81 87 94]