五 常見排序算法

1 十大經典排序算法

2 冒泡排序

1）算法描述

冒泡排序是一種簡單的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。

2）實現步驟

• 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個。
• 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對，這樣在最后的元素應該會是最大的數。
• 針對所有的元素重復以上的步驟，除了最后一個。
• 重復步驟1~3，直到排序完成。

3）優缺點

• 優點：實現和理解簡單。
• 缺點：時間復雜度是O(n^2)，排序元素多時效率比較低。

4）適用范圍

數據已經基本有序，且數據量較小的場景。

5）場景優化

（1）已經有序了還再繼續冒泡問題

• 本輪排序中，元素沒有交換，則isSorted為true，直接跳出大循環，避免后續無意義的重復。

（2）部分已經有序了，下一輪的時候但還是會被遍歷

• 記錄有序和無序數據的邊界，有序的部分在下一輪就不用遍歷了。

（3）只有一個元素不對，但需要走完全部輪排序

• 雞尾酒排序：元素的比較和交換是雙向的，就像搖晃雞尾酒一樣。

3 歸并排序

1）算法描述

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個非常典型的應用。遞歸的把當前序列分割成兩半（分割），在保持元素順序的同時將上一步得到的子序列集成到一起（歸并），最終形成一個有序數列。

2）實現步驟

圖源：https://www.cnblogs.com/chengxiao/p/6194356.html

• 把長度為n的輸入序列分成兩個長度為n/2的子序列。
• 對這兩個子序列分別采用歸并排序。
• 將兩個排序好的子序列合并成一個最終的排序序列。

3）優缺點

優點：

• 性能好且穩定，時間復雜度為O(nlogn) 。
• 穩定排序，適用場景更多。

缺點：

• 非原地排序，空間復雜度高。

4）適用范圍

大數據量且期望要求排序穩定的場景。

4 快速排序

1）算法描述

快速排序使用分治法策略來把一個序列分為較小和較大的2個子序列，然后遞歸地排序兩個子序列，以達到整個數列最終有序。

2）實現步驟

• 從數列中挑出一個元素，稱為 “基準值”（pivot）。
• 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作。
• 遞歸地對【小于基準值元素的子數列】和【大于基準值元素的子數列】進行排序。

3）優缺點

優點：

• 性能較好，時間復雜度最好為O(nlogn)，大多數場景性能都接近最優。
• 原地排序，時間復雜度優于歸并排序。

缺點：

• 部分場景，排序性能最差為O(n^2)。
• 不穩定排序。

4）適用范圍

大數據量且不要求排序穩定的場景。

5）場景優化

（1）每次的基準元素都選中最大或最小元素

• 隨機選擇基準元素，而不是選擇第一個元素。
• 三數取中法，隨機選擇三個數，取中間數為基準元素。

（2）數列含有大量重復數據

• 大于、小于、等于基準值。

（3）快排的性能優化

• 雙軸快排：2個基準數，例子：Arrays.sort() 。

5 堆排序

1）算法描述

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。

2）實現步驟

• 將初始待排序關鍵字序列(R1,R2….Rn)構建成最大堆，此堆為初始的無序區。
• 將堆頂元素R[1]與最后一個元素R[n]交換，此時得到新的無序區(R1,R2,……Rn-1)和新的有序區(Rn),且滿足R[1,2…n-1]<=R[n]。
• 由于交換后新的堆頂R[1]可能違反堆的性質，因此需要對當前無序區(R1,R2,……Rn-1)調整為新堆，然后再次將R[1]與無序區最后一個元素交換，得到新的無序區(R1,R2….Rn-2)和新的有序區(Rn-1,Rn)。不斷重復此過程直到有序區的元素個數為n-1，則整個排序過程完成。

3）優缺點

優點：

• 性能較好，時間復雜度為O(nlogn)。
• 時間復雜度比較穩定。
• 輔助空間復雜度為O(1)。

缺點：

• 數據變動的情況下，堆的維護成本較高。

4）適用范圍

數據量大且數據呈流式輸入的場景。

5）為什么實際情況快排比堆排快？

堆排序的過程可知，建立最大堆后，會將堆頂的元素和最后一個元素對調，然后讓那最后一個元素從頂上往下沉到恰當的位置，因為底部的元素一定是比較小的，下沉的過程中會進行大量的近乎無效的比較。所以堆排雖然和快排一樣復雜度都是O(NlogN)，但堆排復雜度的常系數更大。

6 計數排序

1）算法描述

計數排序不是基于比較的排序算法，其核心在于將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。

2）實現步驟

• 找出待排序的數組中最大元素。
• 構建一個數組C，長度為最大元素值+1。
• 遍歷無序的隨機數列，每一個整數按照其值對號入座，對應數組下標的值加1。
• 遍歷數組C，輸出數組元素的下標值，元素的值是幾就輸出幾次。

3）優缺點

優點：

• 性能完爆比較排序，時間復雜度為O(n+k)，k為數列最大值。
• 穩定排序。

缺點：

• 適用范圍比較狹窄。

4）適用范圍

數列元素是整數，當k不是很大且序列比較集中時適用。

5）場景優化

（1）數字不是從0開始，會存在空間浪費的問題

• 數列的最小值作為偏移量，以數列最大值-最小值+1作為統計數組的長度。

7 桶排序

1）算法描述

桶排序是計數排序的升級版。它利用了函數的映射關系，高效與否的關鍵就在于這個映射函數的確定。實現原理：假設輸入數據服從均勻分布，將數據分到有限數量的桶里，每個桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排序）。

2）實現步驟

• 創建桶，區間跨度=(最大值-最小值)/(桶的數量-1)。
• 遍歷數列，對號入座。
• 每個桶內進行排序，可選擇快排等。
• 遍歷所有的桶，輸出所有元素。

3）優缺點

優點：

• 最優時間復雜度為O(n)，完爆比較排序算法。

缺點：

• 適用范圍比較狹窄。
• 時間復雜度不穩定。

4）適用范圍

數據服從均勻分布的場景。

8 性能對比

隨機生成區間0 ~ K之間的序列，共計N個數字，利用各種算法進行排序，記錄排序所需時間。