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

五 常見排序算法

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

2 冒泡排序

1）算法描述

冒泡排序是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤就把它們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

2）實(shí)現(xiàn)步驟

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

3）優(yōu)缺點(diǎn)

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

4）適用范圍

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

5）場(chǎng)景優(yōu)化

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

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

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

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

（3）只有一個(gè)元素不對(duì)，但需要走完全部輪排序

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

3 歸并排序

1）算法描述

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

2）實(shí)現(xiàn)步驟

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

• 把長(zhǎng)度為n的輸入序列分成兩個(gè)長(zhǎng)度為n/2的子序列。
• 對(duì)這兩個(gè)子序列分別采用歸并排序。
• 將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列。

3）優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

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

缺點(diǎn)：

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

4）適用范圍

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

4 快速排序

1）算法描述

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

2）實(shí)現(xiàn)步驟

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

3）優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

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

缺點(diǎn)：

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

4）適用范圍

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

5）場(chǎng)景優(yōu)化

（1）每次的基準(zhǔn)元素都選中最大或最小元素

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

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

• 大于、小于、等于基準(zhǔn)值。

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

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

5 堆排序

1）算法描述

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

2）實(shí)現(xiàn)步驟

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

3）優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

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

缺點(diǎn)：

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

4）適用范圍

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

5）為什么實(shí)際情況快排比堆排快？

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

6 計(jì)數(shù)排序

1）算法描述

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

2）實(shí)現(xiàn)步驟

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

3）優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

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

缺點(diǎn)：

• 適用范圍比較狹窄。

4）適用范圍

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

5）場(chǎng)景優(yōu)化

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

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

7 桶排序

1）算法描述

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

2）實(shí)現(xiàn)步驟

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

3）優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

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

缺點(diǎn)：

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

4）適用范圍

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

8 性能對(duì)比

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