算法復習——6種排序方法的簡單回顧

常見排序方法：冒泡排序、選擇排序、插入排序、堆排序、歸并排序、快速排序的簡單回顧

冒泡排序

重復“從序列右邊開始比較相鄰兩個數字的大小,再根據結果交換兩個數字的位置”

在冒泡排序中，第 1 輪需要比較 n - 1 次，第 2 輪需要比較 n - 2 次…第 n - 1 輪需要比較 1 次。因此，總的比較次數為 (n - 1) + (n - 2) + … + 1≈n2/2。

時間復雜度：O(n2)

選擇排序

重復“從待排序的數據中尋找最小值,將其與序列最左邊的數字進行交換”

使用線性查找在數據中尋找最小值，找到最小值1。（詳見下一篇文章：數組的查找：線性查找，二分查找）

與最左端數字6交換，即可完成此次操作。

在余下的數字中尋找最小值，重復以上操作：

比較次數：(n - 1) + (n - 2) + … + 1≈n2/2 次

時間復雜度：O(n2)

插入排序

從序列左端開始依次對數據進行排序。插入排序的思路就是從右側的未排序區域內取出一個數據，然后將它插入到已排序區域內合適的位置上。

首先先排好5在第一個位置。從待排數字（未排序區域）中取出最左邊的數字 3，將它與左邊已歸位的數字進行比較。若左邊的數字更大，就交換這兩個數字。重復該操作，直到左邊已歸位的數字比取出的數字更小，或者取出的數字已經被移到整個序列的最左邊為止。

時間復雜度：O(n2)

堆排序

利用了數據結構中的堆。關于堆的介紹可以見上一章：數據結構復習-CSDN博客

首先,在堆中存儲所有的數據,并按降序來構建堆。

取出第一個數字后，重新構造堆。

重復上述操作直到堆變空為止。

時間復雜度：O(nlogn)

雖然運行時間短，但數據結構相對復雜，實現起來相對困難。

歸并排序

把序列分成長度相同的兩個子序列，當無法繼續往下分時（也就是每個子 序列中只有一個數據時），就對子序列進行歸并。

歸并：把兩個排好序的子序列合并成一個有序序列。

將序列逐次分割。分割完畢后，按從小到大順序合并。

合并這種含有多個數字的子序列時,要先比較首位數字,再移動較小的數字。

歸并排序中，分割序列所花費的時間不算在運行時間內（可以當作序列本來就是分割好的）

無論哪一行都是n個數據,所以每行的運行時間都為 O(n)。而將長度為 n 的序列對半分割直到只有一個數據為止時,可以分成 log2n 行。

時間復雜度：O(nlogn)

快速排序

首先會在序列中隨機選擇一個基準值(pivot),然后將除了基準值以外的數分為“比基準值小的數”和“比基準值大的數”這兩個類別,再將其排列成以下形式。

[ 比基準值小的數 ] 基準值 [ 比基準值大的數 ]

接著,對兩個“[ ]”中的數據進行排序之后,整體的排序便完成了。對“[ ]”里面的數據進行排序時同樣也會使用快速排序。

舉例：隨機取4為基準值。將其他數字和基準值進行比較。小于基準值的往左移,大于基準值的往右移。

完成后，再分別對左邊和右邊的數據進行快速排序，就能完成整體的排序。

快速排序是一種**“分治法”**。它將原本的問題分成兩個子問題(比基準值小的數和比基準值大的數),然后再分別解決這兩個問題。

像這樣,在算法內部繼續使用該算法的現象被稱為**“遞歸”**。

時間復雜度：O(nlogn)（如果數據中的每個數字被選為基準值的概率都相等，平均運行時間）

參考資料：我的第一本算法書 (石田保輝 宮崎修一)