簡述幾種常用的排序演算法

摘要：歸并排序和快速排序是兩種稍微復雜的排序演算法，它們用的都是分治的思想，代碼都通過遞回來實作，程序非常相似，理解歸并排序的重點是理解遞推公式和 merge() 合并函式，

本文分享自華為云社區《深入淺出八種排序演算法》，作者：嵌入式視覺 ，

歸并排序和快速排序是兩種稍微復雜的排序演算法，它們用的都是分治的思想，代碼都通過遞回來實作，程序非常相似，理解歸并排序的重點是理解遞推公式和 merge() 合并函式，

一，冒泡排序（Bubble Sort）

排序演算法是程式員必須了解和熟悉的一類演算法，排序演算法有很多種，基礎的如：冒泡、插入、選擇、快速、歸并、計數、基數和桶排序等，

冒泡排序只會操作相鄰的兩個資料，每次冒泡操作都會對相鄰的兩個元素進行比較，看是否滿足大小關系要求，如果不滿足就讓它倆互換，一次冒泡會讓至少一個元素移動到它應該在的位置，重復 n 次，就完成了 n 個資料的排序作業，

總結：如果陣列有 n 個元素，最壞情況下，需要進行 n 次冒泡操作，

基礎的冒泡排序演算法的 C++ 代碼如下：

// 將資料從小到大排序
void bubbleSort(int array[], int n){
 if (n<=1) return;
 for(int i=0; i<n; i++){
 for(int j=0; j<n-i; j++){
 if (temp > a[j+1]){
                temp = array[j]
                a[j] = a[j+1];
                a[j+1] = temp;
 }
 }
 }
}

實際上，以上的冒泡排序演算法還可以優化，當某次冒泡操作已經不再進行資料交換時，說明陣列已經達到有序，就不需要再繼續執行后續的冒泡操作了，優化后的代碼如下：

// 將資料從小到大排序
void bubbleSort(int array[], int n){
 if (n<=1) return;
 for(int i=0; i<n; i++){
 // 提前退出冒泡回圈發標志位
        bool flag = False;
 for(int j=0; j<n-i; j++){
 if (temp > a[j+1]){
                temp = array[j]
                a[j] = a[j+1];
                a[j+1] = temp;
                flag = True; // 表示本次冒泡操作存在資料交換
 }
 }
 if(!flag) break; // 沒有資料交換，提交退出
 }
}

冒泡排序的特點：

1. 冒泡程序只涉及相鄰元素的交換，只需要常量級的臨時空間，故空間復雜度為 O(1)O(1)，是原地排序演算法，
2. 當有相鄰的兩個元素大小相等的時候，我們不做交換，相同大小的資料在排序前后不會改變順序，所以是穩定排序演算法，
3. 最壞情況和平均時間復雜度都為 O(n2)O(n2)，最好時間復雜度是 O(n)O(n)，

二，插入排序（Insertion Sort）

1. 插入排序演算法將陣列中的資料分為兩個區間：已排序區間和未排序區間，最初始的已排序區間只有一個元素，就是陣列的第一個元素，
2. 插入排序演算法的核心思想就是取未排序區間的一個元素，在已排序區間中找到一個合適的位置插入，并保證已排序區間資料一直有序，
3. 重復這個程序，直到未排序區間元素為空，則演算法結束，

插入排序和冒泡排序一樣，也包含兩種操作，一種是元素的比較，一種是元素的移動，

當我們需要將一個資料 a 插入到已排序區間時，需要拿 a 與已排序區間的元素依次比較大小，找到合適的插入位置，找到插入點之后，我們還需要將插入點之后的元素順序往后移動一位，這樣才能騰出位置給元素 a 插入，

插入排序的 C++ 代碼實作如下：

void InsertSort(int a[], int n){
 if (n <= 1) return;
 for (int i = 1; i < n; i++) // 未排序區間范圍
 {
        key  = a[i]; // 待排序第一個元素
        int j = i - 1; // 已排序區間末尾元素
 // 從尾到頭查找插入點方法
 while(key < a[j] && j >= 0){ // 元素比較
            a[j+1] = a[j]; // 資料向后移動一位
            j--;
 }
        a[j+1] = key; // 插入資料
 }
}

插入排序的特點：

1. 插入排序并不需要額外存盤空間，空間復雜度是 O(1)O(1)，所以插入排序也是一個原地排序演算法，
2. 在插入排序中，對于值相同的元素，我們可以選擇將后面出現的元素，插入到前面出現元素的后面，這樣就可以保持原有的前后順序不變，所以插入排序是穩定的排序演算法，
3. 最壞情況和平均時間復雜度都為 O(n2)O(n2)，最好時間復雜度是 O(n)O(n)，

三，選擇排序（Selection Sort）

選擇排序演算法的實作思路有點類似插入排序，也分已排序區間和未排序區間，但是選擇排序每次會從未排序區間中找到最小的元素，將其放到已排序區間的末尾，

選擇排序的最好情況時間復雜度、最壞情況和平均情況時間復雜度都為 O(n2)O(n2)，是原地排序演算法，且是不穩定的排序演算法，

選擇排序的 C++ 代碼實作如下：

void SelectSort(int a[], int n){
 for(int i=0; i<n; i++){
        int minIndex = i;
 for(int j = i;j<n;j++){
 if (a[j] < a[minIndex]) minIndex = j;
 }
 if (minIndex != i){
            temp = a[i]; 
            a[i] = a[minIndex];
            a[minIndex] = temp;
 }
 }
}

冒泡插入選擇排序總結

這三種排序演算法，實作代碼都非常簡單，對于小規模資料的排序，用起來非常高效，但是在大規模資料排序的時候，這個時間復雜度還是稍微有點高，所以更傾向于用時間復雜度為 O(nlogn)O(nlogn) 的排序演算法，

特定演算法是依賴特定的資料結構的，以上三種排序演算法，都是基于陣列實作的，

四，歸并排序（Merge Sort）

歸并排序的核心思想比較簡單，如果要排序一個陣列，我們先把陣列從中間分成前后兩部分，然后對前后兩部分分別排序，再將排好序的兩部分合并在一起，這樣整個陣列就都有序了，

歸并排序使用的是分治思想，分治，顧名思義，就是分而治之，將一個大問題分解成小的子問題來解決，小的子問題解決了，大問題也就解決了，

分治思想和遞回思想有些類似，分治演算法一般用遞回實作，分治是一種解決問題的處理思想，遞回是一種編程技巧，這兩者并不沖突，

知道了歸并排序用的是分治思想，而分治思想一般用遞回實作，接下來的重點就是如何用遞回實作歸并排序，寫遞回代碼的技巧就是，分析問題得出遞推公式，然后找到終止條件，最后將遞推公式翻譯成遞回代碼，所以，要想寫出歸并排序的代碼，得先寫出歸并排序的遞推公式，

遞推公式：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
終止條件：
p >= r 不用再繼續分解，即區間陣列元素為 1 

歸并排序的偽代碼如下：

merge_sort(A, n){
 merge_sort_c(A, 0, n-1)
}
merge_sort_c(A, p, r){
 // 遞回終止條件
 if (p>=r) then return
 // 取 p、r 中間的位置為 q
    q = (p+r)/2
 // 分治遞回
 merge_sort_c(A[p, q], p, q)
 merge_sort_c(A[q+1, r], q+1, r)
 // 將A[p...q]和A[q+1...r]合并為A[p...r]  
 merge(A[p...r], A[p...q], A[q+1...r])
}

4.1，歸并排序性能分析

1，歸并排序是一個穩定的排序演算法，分析：偽代碼中 merge_sort_c() 函式只是分解問題并沒有涉及移動元素和比較大小，真正的元素比較和資料移動在 merge() 函式部分，在合并程序中保證值相同的元素合并前后的順序不變，歸并排序排序就是一個穩定的排序演算法，

2，歸并排序的執行效率與要排序的原始陣列的有序程度無關，所以其時間復雜度是非常穩定的，不管是最好情況、最壞情況，還是平均情況，時間復雜度都是 O(nlogn)O(nlogn)，分析：不僅遞回求解的問題可以寫成遞推公式，遞回代碼的時間復雜度也可以寫成遞推公式：

3，空間復雜度是 O(n)，分析：遞回代碼的空間復雜度并不能像時間復雜度那樣累加，盡管演算法的每次合并操作都需要申請額外的記憶體空間，但在合并完成之后，臨時開辟的記憶體空間就被釋放掉了，在任意時刻，CPU 只會有一個函式在執行，也就只會有一個臨時的記憶體空間在使用，臨時記憶體空間最大也不會超過 n 個資料的大小，所以空間復雜度是 O(n)O(n)，

五，快速排序（Quicksort）

快排的思想是這樣的：如果要排序陣列中下標從 p 到 r 之間的一組資料，我們選擇 p 到 r 之間的任意一個資料作為 pivot（磁區點），我們遍歷 p 到 r 之間的資料，將小于 pivot 的放到左邊，將大于 pivot 的放到右邊，將 pivot 放到中間，經過這一步驟之后，陣列 p 到 r 之間的資料就被分成了三個部分，前面 p 到 q-1 之間都是小于 pivot 的，中間是 pivot，后面的 q+1 到 r 之間是大于 pivot 的，

根據分治、遞回的處理思想，我們可以用遞回排序下標從 p 到 q-1 之間的資料和下標從 q+1 到 r 之間的資料，直到區間縮小為 1，就說明所有的資料都有序了，

遞推公式如下：

遞推公式：
quick_sort(p,r) = quick_sort(p, q-1) + quick_sort(q, r)
終止條件：
p >= r

歸并排序和快速排序總結

歸并排序和快速排序是兩種稍微復雜的排序演算法，它們用的都是分治的思想，代碼都通過遞回來實作，程序非常相似，理解歸并排序的重點是理解遞推公式和 merge() 合并函式，同理，理解快排的重點也是理解遞推公式，還有 partition() 磁區函式，

除了以上 5 種排序演算法，還有 3 種時間復雜度是 O(n)O(n) 的線性排序演算法：桶排序、計數排序、基數排序，這八種排序演算法性能總結如下圖：

參考資料

• 排序（上）：為什么插入排序比冒泡排序更受歡迎？
• 排序（下）：如何用快排思想在O(n)內查找第K大元素？

點擊關注，第一時間了解華為云新鮮技術~

標籤：其他

上一篇：我用ChatGPT做WebRTC音視頻性能優化，主打一個高效

下一篇：3年經驗去面試20k測驗崗，看到這樣的面試題我還是心虛了....