聲明：算法和數(shù)據(jù)結(jié)構(gòu)的文章均是作者從github上翻譯過(guò)來(lái)菇晃，為方便大家閱讀册倒。如果英語(yǔ)閱讀能力強(qiáng)的朋友，可以直接到swift算法俱樂(lè)部查看所有原文磺送，以便快速學(xué)習(xí)驻子。作者同時(shí)也在學(xué)習(xí)中灿意，歡迎交流

插入排序算法的目的：將一個(gè)無(wú)序數(shù)組按照升序或者降序排列起來(lái)。

當(dāng)你得到一個(gè)無(wú)序數(shù)組崇呵，并需要將該數(shù)組按照需求進(jìn)行排序時(shí)缤剧，插入排序算法會(huì)按照以下步驟執(zhí)行實(shí)現(xiàn)：

1.將所有數(shù)字放在一起，我們假設(shè)此時(shí)所有的數(shù)字被無(wú)序但又整齊的排列在一個(gè)通道上域慷。
2.從通道上隨意取出一個(gè)數(shù)字荒辕，可以從最前端取，也可以從最后端去犹褒，無(wú)所謂抵窒。不過(guò)最簡(jiǎn)單的每次都從最前端取出。
3.將取出來(lái)的數(shù)字放入新的數(shù)組里面化漆。
4.從通道中取出第二個(gè)數(shù)字并且插入第三步建立的新數(shù)組里面估脆，根據(jù)升降序?qū)⑿聰?shù)字放在第一個(gè)數(shù)字的前面或者后面，得到一個(gè)有順序的數(shù)組座云。
5.繼續(xù)從通道中取出新數(shù)字疙赠，根據(jù)大小插入到新數(shù)組合適的位置。
6.重復(fù)以上步驟直到通道中沒(méi)有數(shù)字朦拖，排序完畢圃阳，新的數(shù)組就是我們得到的排序好的數(shù)組。

例子

我們需要整理一個(gè)無(wú)序數(shù)組為［8璧帝，3捍岳，5，4睬隶，6］锣夹。
取出第一個(gè)數(shù)字8，得到新的數(shù)組［8］苏潜。無(wú)序數(shù)組變?yōu)椋?银萍，5，4恤左，6］贴唇。
取出第二個(gè)數(shù)字3，插入新的數(shù)組里飞袋，3比8小戳气，得到［3，8］巧鸭。無(wú)序數(shù)組變?yōu)椋?瓶您，4，6］。
取出第三個(gè)數(shù)字5览闰，插入新的數(shù)組里芯肤，5比3大，比8小压鉴，得到［3，5锻拘，8］油吭。無(wú)序數(shù)組變?yōu)椋?，6］署拟。
取出第四個(gè)數(shù)字4婉宰，插入新的數(shù)組里，4比3大推穷，比5小心包，得到［3，4馒铃，5蟹腾，8］。無(wú)序數(shù)組變?yōu)椋?］区宇。
最后取出6娃殖，插入新數(shù)組里，6比5大议谷，比8小炉爆，得到［3，4卧晓，5芬首，6，8］逼裆。排序完成郁稍。

原地排序

我們剛才對(duì)插入排序算法的解釋，可能會(huì)讓大家誤以為插入排序必須要有兩個(gè)數(shù)組配合完成波附，一個(gè)放無(wú)序數(shù)組艺晴，一個(gè)為有序數(shù)組。其實(shí)不然掸屡，我們可以對(duì)一個(gè)無(wú)序數(shù)組直接進(jìn)行原地排序封寞，不需要多建一個(gè)數(shù)組。這里我們需要注意的就是區(qū)分開(kāi)數(shù)組里已排序和未排序的部分仅财。

還是剛才的數(shù)組［8狈究，3，5盏求，4抖锥，6］亿眠。這次我們用｜來(lái)劃分?jǐn)?shù)組中已排序和未排序。

［ ｜8磅废，3纳像，5，4拯勉，6］

我們從左向右開(kāi)始整理數(shù)組竟趾，｜放在最前面，此時(shí)已整理部分為空宫峦。當(dāng)我們開(kāi)始向右移動(dòng)｜岔帽，我們得到

［ 8｜3，5导绷，4犀勒，6］

此時(shí)｜左邊為已經(jīng)整理好的部分［8］，右邊為未整理的部分［3妥曲，5贾费，4，6］逾一。繼續(xù)向右移動(dòng)｜直到未整理部分為空铸本，總體過(guò)程如下：

［｜8，3遵堵，5箱玷，4，6 ］
［ 8｜3陌宿，5锡足，4，6 ］
［ 3壳坪，8｜5舶得，4，6 ］
［ 3爽蝴，5沐批，8｜4，6 ］
［ 3蝎亚，4九孩，5，8｜6 ］
［ 3发框，4躺彬，5，6，8｜］

如何插值

在原地排序過(guò)程中宪拥，我們每次向右移動(dòng)｜仿野，都會(huì)將未排序部分最前端的數(shù)字放入已排序部分，但是我們必須將這個(gè)數(shù)字被放在已排序數(shù)組中合適的位置她君，才能保證左邊的部分依然是排序好的脚作。那么，這個(gè)過(guò)程是如何實(shí)現(xiàn)的缔刹？

仍然是剛才的例子鳖枕，假設(shè)此時(shí)數(shù)組已經(jīng)整理了一部分，狀態(tài)如下：

［ 3桨螺，5，8｜4酿秸，6 ］

下一個(gè)插入的數(shù)值是4灭翔，左側(cè)已整理數(shù)組為［3，5辣苏，8］肝箱。先將｜向右移動(dòng)一個(gè)位置，讓4進(jìn)入左側(cè)區(qū)域稀蟋，此時(shí)煌张，我們將4與其左側(cè)數(shù)字8（已排序好數(shù)組里最大的）進(jìn)行比較：

［ 3，5退客，8骏融，4｜6 ］
           ^

4比8小，所以4應(yīng)該在8前面萌狂，將兩個(gè)數(shù)字交換位置：

［ 3档玻，5，4茫藏，8｜6 ］
        <-->
        交換

我們繼續(xù)4和左側(cè)數(shù)字5進(jìn)行對(duì)比误趴，4比5小，所以4應(yīng)該在5前面务傲，繼續(xù)交換位置：

［ 3凉当，4，5售葡，8｜6 ］
     <-->
     交換

再次對(duì)比4和左側(cè)數(shù)字3看杭，4比3大，不需要交換位置天通，此時(shí)左側(cè)數(shù)組又變成排序好的數(shù)組泊窘。

以上過(guò)程為插入排序算法的內(nèi)循環(huán)描述，在下一部分的代碼中會(huì)體現(xiàn)出來(lái)『姹總體過(guò)程就是將右側(cè)數(shù)值放入左側(cè)已排序數(shù)組的最右端瓜贾，然后通過(guò)大小比較不斷地交換位置，直到結(jié)束携悯。

代碼

func insertionSort(_ array: [Int]) -> [Int] {
  var a = array                             // 1
  for x in 1..<a.count {                    // 2
    var y = x
    while y > 0 && a[y] < a[y - 1] {        // 3
      swap(&a[y - 1], &a[y])
      y -= 1
    }
  }
  return a
}

可以將上述代碼放在playground并進(jìn)行以下測(cè)試：

let list = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
insertionSort(list)

代碼的運(yùn)行邏輯如下：

1.首先復(fù)制整個(gè)數(shù)組祭芦。這個(gè)步驟是必須的因?yàn)槲覀儾荒苤苯訉?duì)原始數(shù)組的內(nèi)容進(jìn)行修改。就像Swift自己的函數(shù)sort()憔鬼，insertionSort()只會(huì)返回一個(gè)整理好的原始數(shù)組的復(fù)制數(shù)組龟劲。

2.整個(gè)函數(shù)有兩個(gè)循環(huán)。外部循環(huán)按照順序遍歷數(shù)組里的每一個(gè)數(shù)字轴或，同時(shí)每次外部循環(huán)所選擇的數(shù)字昌跌，就是每次｜向右側(cè)移動(dòng)進(jìn)來(lái)的數(shù)字。這里x表示左側(cè)已排序數(shù)組最后一位數(shù)字的位置照雁，記住蚕愤，數(shù)組里從0到x的部分就是已經(jīng)排序好的部分。其余的為未排序的部分饺蚊。

3.內(nèi)部循環(huán)從位于x位置的數(shù)字萍诱，也就是從｜向右移動(dòng)進(jìn)來(lái)的數(shù)字，開(kāi)始不斷向前一位進(jìn)行大小比較污呼，當(dāng)發(fā)現(xiàn)當(dāng)前位置的數(shù)字小于前一位裕坊，立刻向左移動(dòng)并繼續(xù)比較，直到排序結(jié)束燕酷。

去掉交換過(guò)程

上述版本的代碼運(yùn)行效果良好籍凝，但是，我們?nèi)匀豢梢赃M(jìn)行優(yōu)化悟狱，方法就是去掉swap()方程静浴。你已經(jīng)知道我們需要將順序不對(duì)的數(shù)字進(jìn)行位置調(diào)整：

［ 3，5挤渐，4苹享，8｜6 ］
        <-->
        交換
［ 3，4浴麻，5得问，8｜6 ］
     <-->
     交換

去掉圖中的交換過(guò)程，我們可以將圖中需要交換位置的數(shù)字直接向右移動(dòng)软免，然后將新的數(shù)字直接復(fù)制到正確的位置：

[ 3宫纬，5，8膏萧，4｜6 ]   記住4
          ＊

[ 3漓骚，5蝌衔，8，8｜6 ]  將8轉(zhuǎn)移到右側(cè)
        -->

[ 3蝌蹂，5噩斟，5，8｜6 ]  將5轉(zhuǎn)移到右側(cè)
     -->

[ 3孤个，4剃允，5，8｜6 ]  將4復(fù)制粘貼到新的位置
     ＊

代碼如下：

func insertionSort(_ array: [Int]) -> [Int] {
  var a = array
  for x in 1..<a.count {
    var y = x
    let temp = a[y]
    while y > 0 && temp < a[y - 1] {
      a[y] = a[y - 1]                // 1
      y -= 1
    }
    a[y] = temp                      // 2
  }
  return a
}

其中//1表示將需要交換位置的數(shù)字向右移動(dòng)一個(gè)位置齐鲤。在內(nèi)循環(huán)的最后斥废，y是新數(shù)字最后正確的位置的索引，//2就是將新數(shù)字復(fù)制到該位置给郊。

通用化

很顯然牡肉，上述的代碼只適合對(duì)數(shù)字類型的數(shù)據(jù)進(jìn)行排序，但這里我們只需要對(duì)代碼進(jìn)行兩處修改淆九，即可完成對(duì)大部分類型數(shù)據(jù)的排序荚板。首先，函數(shù)名更改如下：

func insertionSort<T>(_ array: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {

此時(shí)數(shù)組的數(shù)據(jù)類型為[T]吩屹，這里的T是通用類型，可以是數(shù)值拧抖，字符串煤搜，或者其他數(shù)據(jù)類型。新的參數(shù)isOrderedBefore: (T, T) -> Bool函數(shù)帶有兩個(gè)T對(duì)象唧席，函數(shù)返回true表示第一個(gè)對(duì)象排在第二個(gè)對(duì)象前面擦盾，返回false則表示第一個(gè)對(duì)象排在第二個(gè)對(duì)象后面。效果等同于Swift自帶函數(shù)sort()淌哟。

第二個(gè)修改的地方是內(nèi)循環(huán):

while y > 0 && isOrderedBefore(temp, a[y - 1]) {

這里我們用isOrderedBefore()取代了temp < a[y - 1]迹卢，它們的目的相同，唯一不一樣的是前者可以對(duì)任何數(shù)據(jù)類型進(jìn)行比較徒仓，不單單是數(shù)字腐碱。

我們可以在playground進(jìn)行以下測(cè)試:

let numbers = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
insertionSort(numbers, <)
insertionSort(numbers, >)

這里<和>表示序列的順序，從小到大或者從大到小掉弛。當(dāng)然我們也可以對(duì)其他數(shù)據(jù)類型進(jìn)行排序症见，比如字符：

let strings = [ "b", "a", "d", "c", "e" ]
insertionSort(strings, <)

或者是更復(fù)雜的對(duì)象：

let objects = [ obj1, obj2, obj3, ... ]
insertionSort(objects) { $0.priority < $1.priority }

這里的閉環(huán)告訴insertionSort()函數(shù)對(duì)對(duì)象的priortity特性進(jìn)行排序。

插值排序?qū)儆诜€(wěn)定排序殃饿。當(dāng)數(shù)組里含有同樣的整理參考對(duì)象的元素在經(jīng)過(guò)整理后仍然保持原來(lái)的順序谋作，我們就說(shuō)這個(gè)排序就是穩(wěn)定的。這個(gè)特性對(duì)于數(shù)值或者字符排序來(lái)說(shuō)并不是很重要乎芳，但是對(duì)于更復(fù)雜的對(duì)象來(lái)說(shuō)就非常重要了遵蚜。正如上面的例子帖池，如果數(shù)組里面的兩個(gè)對(duì)象擁有同樣的priority，我們可以無(wú)視掉它們的其它特性值吭净，不對(duì)它們進(jìn)行位置的調(diào)整睡汹。

性能

當(dāng)數(shù)組是已經(jīng)排序好的數(shù)組，插值排序算法的運(yùn)行速度非吃芮快帮孔。這句話聽(tīng)起來(lái)好像理所當(dāng)然，但是對(duì)于所有搜索算法來(lái)說(shuō)不撑，并不是這樣的文兢。實(shí)際上，在大部分?jǐn)?shù)據(jù)已經(jīng)排序好的前提下焕檬，不是全部姆坚，插值排序依然可以取得不賴的效果。

對(duì)于插值排序算法來(lái)說(shuō)实愚，O(n^2)是它最差和平均性能表現(xiàn)兼呵。因?yàn)樗暮瘮?shù)里含有兩個(gè)循環(huán)。其它類型的排序算法腊敲，比如快速排序和歸并排序击喂，在輸入數(shù)據(jù)量很大的情況下，可以達(dá)到O(nlogn)的效果碰辅。

插值排序?qū)τ谛?shù)據(jù)量的排序來(lái)說(shuō)非扯海快。在一些標(biāo)準(zhǔn)程序庫(kù)里没宾，如果數(shù)據(jù)大小不大于10凌彬，它們會(huì)用插值排序來(lái)取代快速排序。