冒泡、插入、選擇 O(n^2) 基于比較
快排、歸并 O(nlogn) 基于比較
計數、基數、桶 O(n) 不基于比較

總結：如何實現一個通用的高性能的排序函數？

一、如何選擇合適的排序算法？

1.排序算法一覽表

時間復雜度是穩定排序？是原地排序？

冒泡排序 O(n^2)	是	是
插入排序 O(n^2)	是	是
選擇排序 O(n^2)	否	是
快速排序 O(nlogn)	否	是
歸并排序 O(nlogn)	是	否
桶排序 O(n)	是	否
計數排序 O(n+k)，k是數據范圍	是	否
基數排序 O(dn)，d是維度	是	否

2.為什選擇快速排序？
1）線性排序時間復雜度很低但使用場景特殊，如果要寫一個通用排序函數，不能選擇線性排序。
2）為了兼顧任意規模數據的排序，一般會首選時間復雜度為O(nlogn)的排序算法來實現排序函數。
3）同為O(nlogn)的快排和歸并排序相比，歸并排序不是原地排序算法，所以最優的選擇是快排。

二、如何優化快速排序？

導致快排時間復雜度降為O(n)的原因是分區點選擇不合理，最理想的分區點是：被分區點分開的兩個分區中，數據的數量差不多。如何優化分區點的選擇？有2種常用方法，如下：
1.三數取中法
①從區間的首、中、尾分別取一個數，然后比較大小，取中間值作為分區點。
②如果要排序的數組比較大，那“三數取中”可能就不夠用了，可能要“5數取中”或者“10數取中”。
2.隨機法：每次從要排序的區間中，隨機選擇一個元素作為分區點。
3.警惕快排的遞歸發生堆棧溢出，有2中解決方法，如下：
①限制遞歸深度，一旦遞歸超過了設置的閾值就停止遞歸。
②在堆上模擬實現一個函數調用棧，手動模擬遞歸壓棧、出棧過程，這樣就沒有系統棧大小的限制。

三、通用排序函數實現技巧

1.數據量不大時，可以采取用時間換空間的思路
2.數據量大時，優化快排分區點的選擇
3.防止堆棧溢出，可以選擇在堆上手動模擬調用棧解決
4.在排序區間中，當元素個數小于某個常數是，可以考慮使用O(n^2)級別的插入排序
5.用哨兵簡化代碼，每次排序都減少一次判斷，盡可能把性能優化到極致

四、思考

1.Java中的排序函數都是用什么排序算法實現的？有有哪些技巧？
查看了Java的Arrays.sort
回答１：
1.若數組元素個數總數小于47，使用插入排序
2.若數據元素個數總數在47~286之間，使用快速排序。應該是使用的優化版本的三值取中的優化版本。
3.若大于286的個數，使用歸并算法排序。
回答２：

對于基本類型的數組，Java 采用的是雙樞軸快速排序（Dual-Pivot Quicksort），這個算法是 Java 7 引入的。在此之前，Java 采用的是普通的快速排序，雙樞軸快速排序是對普通快速排序的優化，新算法的實現代碼位于類 java.util.DualPivotQuicksort 中。

對于對象類型，Java 采用的算法是 TimSort，TimSort 算法也是 Java 7 引入的。在此之前，Java 采用的是歸并排序。TimSort 算法實際上是對歸并排序的一系列優化，TimSort 的實現代碼位于類 java.util.TimSort 中。

在這些排序算法中，如果數組長度比較小，它們還會采用效率更高的插入排序。

筆記整理來源： 王爭 數據結構與算法之美

總結

以上是生活随笔為你收集整理的【数据结构与算法】排序优化的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。