時間復雜度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
本文鏈接： https://www.nephen.cn/posts/601fbd5/
著作權宣告： 本博客所有文章除特別宣告外，均采用 CC BY-NC-SA 3.0 許可協議，轉載請注明出處！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/458389.html
標籤：其他
下一篇：stun檢查nat型別