各種排序算法的穩定性,時間複雜度和空間複雜度總結:
我們比較時間複雜度函數的情況:
時間複雜度函數O(n)的增長情況:
所以對於n較大的排序記,一般的選擇都是時間複雜度為O(nlog2n)的排序方法。
時間複雜度來說:
1.平方階O(n2)排序
各類簡單排序:直接插入排序,直接選擇排序和冒泡排序;
2.線性對數階O(nlog2n)排序
快速排序、堆排序和歸併排序;
3.O(n1+§)排序,§是介於0和1之間的整數。
希爾排序;
4.線性階O(n)排序
基數排序,此外還有桶、箱排序。
5.說明
當原表有序或基本有序時,直接插入排序和冒泡排序將大大減少比較次數和移動記錄的次數,時間複雜度可降至O(n);
而快速排序則相反,當原表基本有序時,將蛻化為冒泡排序,時間複雜度提高為O(n2);
表是否有序,對簡單選擇排序、堆排序、歸併排序和基數排序的時間複雜度影響不大。
穩定性來說:
1.排序算法的穩定性:若待排序的序列中,存在多個具有相同關鍵字的記錄,經過排序,這些記錄的相對次序保持不變,則稱該算法是穩定的;若經排序後,記錄的相對次序發生了改變,而稱該算法是不穩定的。
2.穩定性的好處:排序算法如果是穩定的,那麼從一個鍵上排序,然後再從另一個鍵上排序,第一個鍵排序的結果可以為第二個鍵排序所用。基數排序就是這樣,先按低位排序,逐次按高位排序,低位相同的元素其順序再高位也相同時是不會改變的。另外,如果排序算法穩定,可以便面多餘的比較;
3.穩定的排序算法:冒泡排序,直接插入排序,歸併排序和基數排序;
4.不穩定的排序算法:選擇排序,快速排序,希爾排序,堆排序;
選擇排序算法的準則和依據:
1.準則:每種排序算法都各有優缺點。因此,在實用時需根據不同情況適當選用,甚至可以將多種方法結合起來使用。
2.依據:影響排序算法的因素有很多,平均時間複雜度低的算法並不一定就是最優的。相反,有時平均時間複雜度高的算法可能更適合某些特殊情況。同時,選擇算法時還得考慮它的可讀性,以利於軟件的維護。一般而言,需考慮的因素有以下4點:
1.待排序的記錄數目n的大小;
2.記錄本身數據量的大小,也就是記錄中除關鍵字外的其他信息量的大小;
3.關鍵字的結構及其分佈情況;
4.對排序穩定性的要求。
設待排序元素的個數為n。
1.當n較大,則因採用時間複雜度為O(nlog2n)的排序方法:快速排序、堆排序或歸併排序;
快速排序:是目前基於比較的內部排序中被認為是最好的方法,當待排序的關鍵字是隨機分佈時,快速排序的平均時間最短;
堆排序:如果內存空間允許切要求穩定性的;
歸併排序:它有一定數量的數據移動,所以我們可以與插入排序結合,先獲得一定長度的序列,然後再合併,在效率上有所提高。
2.當n較小,可採用直接插入或直接選擇排序。
直接插入排序:當元素分佈有序,直接插入排序將大大減少比較次數和移動記錄的次數。
直接選擇排序:元素分佈有序,如果不要求穩定性,選直接選擇排序。
3.一般不使用或不直接使用傳統的冒泡排序。
4.基數排序:它是一種穩定的排序算法,但有一定的侷限性:
關鍵字可分解
記錄的關鍵字位數較少,如果密集更好
如果是數字時,最好是無符號的,否則將增加相關的映射覆雜度,可先將其正負分開排序。
閱讀更多 程序員界的彭于晏 的文章