聊一聊插入排序和比較排序

簡介

插入排序和比較排序是排序算法中比較基礎和簡單的兩種于购，其時間復雜度均為 $O(N^{2})$ ，在分析算法時間復雜度時知染，我們往往會只會分析比較開銷肋僧，但是交換開銷也確實存在。這里我將綜合比較開銷和交換開銷控淡，來分析一下插入排序和比較排序的區(qū)別嫌吠，以及何時選擇插入排序？何時該選擇比較排序逸寓？

我之前的文章 排序算法詳解 里給出了幾個基本排序算法的JavaScript版本實現(xiàn)居兆，感興趣的也可以移步。

空間復雜度

插排和選排的均在交換時使用了一個臨時空間竹伸，其空間復雜度均為 $O(1)$ 。而且插排和選排在排序時同時維護了一個已排序的有序列表和一個待排序的無序列表簇宽，不同在于：

插排從無序列表中取第一個數(shù)勋篓，與有序列表的數(shù)依次比較，有序列表的已排數(shù)據(jù)的位置均可能發(fā)生變化魏割。
選排從無序列表中取最小數(shù)譬嚣，只和無序列表中第一個數(shù)交換，此時無序列表第一個數(shù)歸于有序列表（相當于最后一個數(shù)）钞它。

在每一輪排序過程中拜银，均需要有一個臨時空間用來存儲無序列表提取的這一個數(shù)，用于未來的交換遭垛。

時間復雜度

眾所周知尼桶，插排和選排的時間復雜度均為 $O(N^{2})$ 。我們在分析時間復雜度的時候锯仪，其實都是分析的比較時間復雜度泵督，但是計算機做算法的時候除了比較，還有交換庶喜，并不是說交換時間復雜度不重要小腊，而是它大部分情況相對于比較復雜度可以忽略救鲤，至于原因，接下來結(jié)合比較和交換開銷秩冈，來分析插排和選排本缠，自然就明白了。

比較復雜度對比

插入排序
- 最差情況：最差情況下反向有序入问，每一輪插入搓茬，都需要依次比較到有序列表的第一個數(shù)，第一輪比較0次队他，第二輪比較1次卷仑，第N輪比較N-1次。一共比較 $\frac{N \times (N-1)} {2}$ 次麸折，復雜度 $O(N^{2})$
- 最好情況：最好情況下有序锡凝，每一輪插入，都只需要比較1次垢啼，一共比較 $N$ 次窜锯，復雜度 $O(N)$
- 平均情況：平均情況下，每一輪插入芭析，假設依次比較到有序列表的中間位置锚扎，一共比較 $\frac {N \times (N-1)} {4}$ 次，復雜度 $O(N^{2})$
選擇排序

選擇排序比較次數(shù)是固定的馁启，每一輪都需要從待排序的無序列表中選取一個最屑菘住（或最大）的數(shù)，選取中都需要比較到最后一個元素才能得到結(jié)果惯疙。第一輪比較N-1次熊赖，第N輪比較0次督赤。一共比較 $\frac {N \times (N-1)} {2}$ 次芝硬，復雜度 $O(N^{2})$

因此可以得出結(jié)論：在最差情況下事期，兩者復雜度一樣。在最好情況下蒿偎，兩者復雜度差異是比較大的（1個次方）朽们，而在平均情況下，插排的比較次數(shù)也只是選排的一半诉位。這也是關(guān)于插排和選排的通用結(jié)論骑脱，一般情況下插排優(yōu)于選排，主要就在于插排是插入有序列表不从，而選排是需要在無序列表中選擇一個最大值（或最小值）惜姐，想象一下我們斗地主摸牌，摸到一張牌我們是可以馬上從小到大判斷插入到哪的（這里假設只能從小到大比較），而不必每一張牌都對比一下歹袁。

但是上面的結(jié)論只討論了比較復雜度坷衍，其實在為什么說平均情況下，插入排序比選擇排序快? - 莫濤的回答 - 知乎
和Stack Overflow上条舔，也有人對這種回答中不談交換表示疑惑枫耳，下面我們再來分析一下交換復雜度。

交換復雜度對比

插入排序
- 最差情況：每一次比較完都需要交換孟抗。第一輪交換0次迁杨，第二輪交換1次，第N輪交換N-1次凄硼。一共交換 $\frac{N \times (N-1)} {2}$ 次铅协，復雜度 $O(N^{2})$
- 最好情況：每一次比較完都無需交換，總共交換 $0$ 次摊沉，復雜度 $O(0)$
- 平均情況：每一輪都插入到中間位置狐史，總共交換次數(shù)為 $\frac{N \times (N-1)} {4}$ 次，復雜度 $O(N^{2})$
選擇排序
- 最差情況：每一輪都需要交換说墨，總共交換 $N$ 次骏全，復雜度 $O(N)$
- 最好情況：每一輪都無需交換，總共交換 $0$ 次尼斧，復雜度 $O(0)$
- 平均情況：有一半輪次需要交換姜贡，總共交換 $\frac N 2$ 次，復雜度 $O(N)$

交換復雜度的對比中我們可以得出：最好情況下兩者都無需交換棺棵，然而在最差和平均情況下楼咳，插入排序的交換次數(shù)都高于選擇排序，差異為一個次方律秃∨老穑可以看出差異還是很大的，單從這樣來看棒动，是無法忽略其影響的。

影響時間復雜度的其他因素

其實宾添，在《算法導論》一書中還提到了一個算法性能分析依賴的以下要素：

待排項數(shù)

這些項已排序程度

項值的限制

計算機體系結(jié)構(gòu)

使用的存儲設備種類（主存船惨，磁盤或磁帶）

回到這個例子中，我們可以假設忽略硬件的影響缕陕、項值無限制粱锐。而已排序程度隨機（也就是選用平均復雜度，不過一般算法分析都采用最壞情況下的復雜度作為瓶頸進行分析）扛邑，因此分析要素只剩下待排項數(shù)N怜浅，可以使用上面的分析給出結(jié)論。

結(jié)論

插入排序和比較排序誰更優(yōu)？主要在于比較開銷和交換開銷的量級：

如果兩者量級相當恶座，則插入排序優(yōu)于選擇排序
如果比較開銷量級小于交換開銷搀暑，則選擇排序優(yōu)于插入排序
如果比較開銷量級大于交換開銷，如果差別不大則難以比較跨琳，如果差異較大自点，則可以忽略交換復雜度，此時插入排序優(yōu)于選擇排序

事實上脉让，交換一般直接交換內(nèi)存地址（指針）而不是交換真實的數(shù)據(jù)桂敛，而比較則需要CPU的一些運算。這里的一個回答便給出了自定義賦值函數(shù)溅潜，如果直接交換數(shù)據(jù)术唬，當數(shù)據(jù)量過大，交換開銷大大增加滚澜，此時插入排序反而不如選擇排序粗仓，因為其交換次數(shù)平均情況下和選擇排序不在一個量級。

當然博秫，由于交換排序進行了過多的交換次數(shù)（也就是寫操作）潦牛，如果使用Flash Memory，則需要額外注意挡育，因為Flash Memory的擦除次數(shù)有限巴碗，過多的寫操作會消耗其擦除次數(shù)，從而消耗Flash Memory的壽命即寒。

總結(jié) & 參考

一般情況下橡淆，插入排序確實優(yōu)于選擇排序，但也有需要注意的點母赵，而不單單是只判斷比較復雜度那么簡單逸爵。需要我們了解清楚再做判斷。

文章參考了以下資料：

Insertion Sort vs. Selection Sort
為什么說平均情況下凹嘲，插入排序比選擇排序快? - 知乎
When should one use Insertion vs. Selection sort?