排序演算法一
時間複雜度O(n^2)的典型排序演算法有三個，冒泡排序、插入排序和選擇排序，這三個排序演算法最壞時間複雜度都達到了n^2。
冒泡排序是從第一個元素第二個元素開始，每次相鄰的兩個元素做對比，將較大的元素交換上去，這樣一輪下來最大的元素就排到最上面去了，最上面那個元素就固定住了，不參與後面的排序了，再開啟下一輪排序，也是從第一個元素第二個元素開始，進行比較交換操作，將次大的元素排上去，等於是每排一輪就排好一個元素，n輪下來就排好序了。其中每排一輪加起來要比較n-1+n-2+n-3+…+1+0=n*(n-1)/2次，這是最壞的情況，當其中某一輪排序未交換任何元素時，說明全部元素已經是排好序的狀態，所以最好的情況就是排一輪就達到有序狀態，只需要比較n-1次。
插入排序是分兩個區進行處理，一個已排序區，一個未排序區，初始化時已排序區就只有第一個元素，從剩餘的元素即未排序區取第一個元素插入到已排序區的合適位置，讓已排序區始終保持排序的狀態，最壞的情況，從未排序區取一個元素插入到已排序區時，需要從已排序區最末尾一個元素開始比較，一直比較到已排序區的第一個元素，每個未排序元素都要如此比較才能選到已排序區的合適位置，這樣算下來總共需要比較的次數為1+2+3+…+n-1=n*(n-1)/2，其實這就是完全逆序的情況，而最好的情況就是完全有序的情況，每次比較已排序區最末尾一個元素就找到插入的位置了，只要插入到已排序區末尾就行了，總共有n-1次，這樣算下來只需要比較n-1次。
選擇排序也是分已排序區和未排序區進行處理，不過不一樣的是，每次都是從未排序區選擇最小或最大的元素，直接放到已排序區的首部或末尾，說起來和插入排序很類似，但關鍵點在於，從未排序區選擇一個最值，必須遍歷完未排序區全部的元素才行，而插入排序在最好的情況下，只需要插入到已排序區的末尾就行了，所以選擇排序最好最壞時間複雜度都是n-1+n-2+…+1=n*(n-1)/2。
看起來冒泡排序和插入排序時間複雜度都差不多，但其實還有一些細微的差異，主要表現在具體實現上，冒泡排序比較完兩個元素需要進行交換時，需要有三步，int tmp=a; a=b;b=tmp;，而插入排序比較完後，只需要把元素往後移動一位即可，a[i+1]=a[i]，這樣就能把前面的位置空出來，真正找到要插入的位置後，將空出來的這個位置填入要插入的值即可，這樣對比起來，插入排序只需要一步。所以在追求極致性能的情況下，還是優先選擇插入排序。
這三種排序演算法最壞的情況下時間複雜度都達到了O(n^2)，都屬於原地排序演算法，即空間複雜度均為O(1)，不會隨著數據量的變大而變大，但是選擇排序是不穩定的排序演算法，因為每次從未排序區選擇最值後，都會與未排序區的第一個元素進行交換，該未排序區的第一個元素也是緊接著已排序區最後一個元素的位置，如果未排序區的第一個元素為未排序區裡面多個重複元素中的一個，這個元素就會被交換到最值的位置，所以相同元素的位置可能就發生了變化，還是插入排序靠譜，每次都插入到大於等於的元素之後，就能保證相同的元素還是按照原來的順序排列的。
綜上所述，根據排序效率，是否穩定排序等方面來考慮，優先選擇插入排序。
本文作者： nephen
本文鏈接： //www.nephen.cn/posts/601fbd5/
版權聲明： 本部落格所有文章除特別聲明外，均採用 CC BY-NC-SA 3.0 許可協議。轉載請註明出處！
