算法和數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識分享（下）

五 常見排序算法

1 十大經(jīng)典排序算法

2 冒泡排序

1）算法描述

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

2）實現(xiàn)步驟

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

3）優(yōu)缺點

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

4）適用范圍

數(shù)據(jù)已經(jīng)基本有序，且數(shù)據(jù)量較小的場景。

5）場景優(yōu)化

（1）已經(jīng)有序了還再繼續(xù)冒泡問題

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

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

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

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

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

3 歸并排序

1）算法描述

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

2）實現(xiàn)步驟

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

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

3）優(yōu)缺點

優(yōu)點：

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

缺點：

• 非原地排序，空間復(fù)雜度高。

4）適用范圍

大數(shù)據(jù)量且期望要求排序穩(wěn)定的場景。

4 快速排序

1）算法描述

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

2）實現(xiàn)步驟

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

3）優(yōu)缺點

優(yōu)點：

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

缺點：

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

4）適用范圍

大數(shù)據(jù)量且不要求排序穩(wěn)定的場景。

5）場景優(yōu)化

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

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

（2）數(shù)列含有大量重復(fù)數(shù)據(jù)

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

（3）快排的性能優(yōu)化

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

5 堆排序

1）算法描述

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

2）實現(xiàn)步驟

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

3）優(yōu)缺點

優(yōu)點：

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

缺點：

• 數(shù)據(jù)變動的情況下，堆的維護成本較高。

4）適用范圍

數(shù)據(jù)量大且數(shù)據(jù)呈流式輸入的場景。

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

堆排序的過程可知，建立最大堆后，會將堆頂?shù)脑睾妥詈笠粋€元素對調(diào)，然后讓那最后一個元素從頂上往下沉到恰當(dāng)?shù)奈恢茫驗榈撞康脑匾欢ㄊ潜容^小的，下沉的過程中會進行大量的近乎無效的比較。所以堆排雖然和快排一樣復(fù)雜度都是O(NlogN)，但堆排復(fù)雜度的常系數(shù)更大。

6 計數(shù)排序

1）算法描述

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

2）實現(xiàn)步驟

• 找出待排序的數(shù)組中最大元素。
• 構(gòu)建一個數(shù)組C，長度為最大元素值+1。
• 遍歷無序的隨機數(shù)列，每一個整數(shù)按照其值對號入座，對應(yīng)數(shù)組下標(biāo)的值加1。
• 遍歷數(shù)組C，輸出數(shù)組元素的下標(biāo)值，元素的值是幾就輸出幾次。

3）優(yōu)缺點

優(yōu)點：

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

缺點：

• 適用范圍比較狹窄。

4）適用范圍

數(shù)列元素是整數(shù)，當(dāng)k不是很大且序列比較集中時適用。

5）場景優(yōu)化

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

• 數(shù)列的最小值作為偏移量，以數(shù)列最大值-最小值+1作為統(tǒng)計數(shù)組的長度。

7 桶排序

1）算法描述

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

2）實現(xiàn)步驟

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

3）優(yōu)缺點

優(yōu)點：

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

缺點：

• 適用范圍比較狹窄。
• 時間復(fù)雜度不穩(wěn)定。

4）適用范圍

數(shù)據(jù)服從均勻分布的場景。

8 性能對比

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