為什麼說平均情況下，插入排序比選擇排序快?

01-03

如題，求高人細解

平均情況下插入排序需要n*(n-1)/4次比較，選擇排序固定需要n*(n-1)/2次比較

wikipedia：

選擇排序

插入排序

--------------------------------------

選擇的邏輯是「每次在數組中找最小（大）的放到另一個數組的最後一個」，這樣無論數組是什麼樣子的都要遍歷需要排列的數組直到只有最後一個，所以，第一個數字要遍歷n遍，第二個n-1……一直到1.

插入排序法是類似我們打撲克時候理牌，拿到第一張，放在手裡，第二張比較一下，是否大於第一張，大於就放在第一張的後面，這樣第三張可能在掃描到第一張的時候就知道自己的位置，或者第二張，以此類推，第n張可能比較第一張牌，然後直接插到第一張前面，也可能比較到最後一張，插到最後面。

所以選擇排序的比較次數是固定的，而插入不是固定的，那些可能被省掉的操作就是變快的部分。

這個問題取決於兩個方面：

1. 比較開銷

選擇排序的比較開銷是固定的n(n-1)/2,而插入排序平均下來是n(n-1)/4.

2. 交換開銷

選擇排序最多只需要執行2*(n-1)次交換，而插入排序平均的交換開銷也是n(n-1)/4.

這就取決於單次比較和交換的開銷之比。如果是一個量級的，則插入排序優於選擇排序，如果交換開銷遠大於插入開銷，則插入排序可能比選擇排序慢。

====================

下圖是一個簡單的比較，用插入排序，二分插入排序，選擇插入排序和std::sort分別排序三萬個元素的數組。元素分別為int, 有500個int,但賦值函數為預設生成的按內存拷貝的LargeStruct，和有500個int且自定義賦值函數的LargeStructSlowAssign.

縱坐標是取對數之後的時間，以毫秒為單位。

橫坐標是三種不同的數據類型，從左到右分別為int, LargeStruct, LargeStructSlowAssign

每一條線代表一種不同的排序演算法。

從圖中可以看出

對於插入排序（最上面的紅線）,排序時間隨著賦值函數的開銷上升而上升很明顯。
即使是經過優化的二分插入排序（圖中橙線），在賦值函數開銷太大時相對於普通插入排序的優勢幾乎可以忽略。
選擇排序對賦值函數的開銷很不敏感（圖中上方藍線）。在賦值函數開銷很低的時候插入排序佔優，隨著賦值函數開銷上升，選擇排序性能就勝過插入排序。
標準庫的std::sort（圖中最下方深藍色線）若是基於快排，則swap操作也沒有那麼多，受賦值函數的開銷影響也沒那麼大。

====================

實際上也就是對c++有這問題，如果其他語言直接交換引用或指針就沒這問題了，當然在c++中也可以通過指針來降低交換開銷。這種情況下插入排序就比選擇排序快了。

====================

測試代碼： misc/sort.cpp at master · QAMichaelPeng/misc · GitHub

先來說選擇排序的原理和實現。

注意到外循環中的out是已經排好隊列的數據，是每一輪內循環中的不變數和初始量。剛開始out=0；內循環中，初始化in = out +1；即是不變數旁邊的數據；內循環中，將還沒排好的數據和已經排好的數據的最大值相比，如果在還沒排好的數據中找到一個數據比已經排好的數據小，那就交換這兩個數。這樣就可以保證，在已經排好的數據裡面，都比還沒排好的數據小。可以看得出來，每次需要比較的數據會逐漸減少，直到最後比較最後兩個數據即可。演算法複雜度是(n-1)+(n-2)+....+2+1 =n*(n-1)/2。雖然演算法複雜度和冒泡排序一樣，都是O(n*n),但由於交換數據少，執行起來會快很多，因為交換數據比比較數據所需要的時間多很多。

再來說插入排序的原理和實現

插入排序的演算法複雜度也是O(n*n)，但它的執行速度比冒泡排序快2倍，大多數情況下也比選擇排序快。

在插入排序裡面，我們把原有的數據看做成已經部分排列好的數據，我們要做的是把還沒排列好的數據插入到已經排好的數據中來。這是插入排序的基本思路。

在計算機里是這樣實現的，先把第一數據看做成已經排序好的數據，設置out =1，第二個數據看做成「Marked」 player；先將Marked player 複製一份放到temp中，如果第一個數據比第二個數據大，那就把第一個數據往右移動，把第二個數據放到第一個數據移動後留出來的空白里。這樣第一二個數據都排序好了。然後out ++；

在外循環里，out從1開始增加，一直移動到最右邊，從out到最右邊的數據都是還沒排序好的數據。在內循環的while loop裡面，in的起點是out，然後向左移動，直到找到比temp大的數據，然後把temp插入到這個數據的前面。

它的演算法複雜度可以這樣算，第一次只需要比較1位，第二次比較2位，第三次比較3位，最後一次比較n-1位，需要比較的次數= 1+2+3+4+...+n = n*(n-1)/2; 但是其實在找到插入點之前，平均只需要比較一半的數據即可，不需要全部比較。所以我們可以再將比較的次數除以2，得到n*(n-1)/4。

雖然複製的次數和其他的排序一樣，但複製比不如交換那麼費時間。所以總的來說，一般情況下，插入排序比選擇排序快一倍。

（1）選擇排序是最機械的一種排序，在排序的過程中完全不考慮原始序列的任何排序情況，只是機械的從剩餘的序列中選擇出最大/最小的元素，無論初始序列是什麼樣的排列方式，選擇排序都得經過N(N-1)/2次比較。

（2）插入排序的時間跟原始序列的排序方式有關，最差的情況是原始序列完全倒序，需要N(N-1)/2次比較；最好的情況是原始序列完全正序，時間複雜度只需要N次比較；

平均下來顯然插入排序要快一點。