0. 排序算法概述

十種常見排序算法可以分為兩大類：

• 比較類排序：通過比較來決定元素間的相對次序，由于其時間復雜度不能突破O(nlogn)，因此也稱為非線性時間比較類排序。
• 非比較類排序：不通過比較來決定元素間的相對次序，它可以突破基于比較排序的時間下界，以線性時間運行，因此也稱為線性時間非比較類排序。

1. 選擇排序（Selection Sort）

基本思想：

首先找到數(shù)組中最小的那個元素，將它和數(shù)組的第一個元素交換位置。然后在剩下的元素中找到最小的元素，將它與數(shù)組的第二個元素交換位置。如此往復，直到將整個數(shù)組排序。

代碼實現(xiàn)：

// 兩數(shù)交換
void mySwap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}

// 選擇排序
void SelectionSort(vector<int> &num) {
	int len = num.size();
    for (int i = 0; i < len - 1; ++i) {
        int minPos = i;
        for (int j = i + 1; j < len; ++j) {
            if (num[j] < num[minPos])
                minPos = j;
        }
        
        mySwap(num[i], num[minPos]);
    }
}

算法分析：

• 時間復雜度：$O(n^2)$

• 空間復雜度：$O(1)$

• 穩(wěn)定性：不穩(wěn)定排序

2. 直接插入排序（Insertion Sort）

基本思想：

把第一個元素作為有序部分，從第二個元素開始將剩余元素逐個插入有序部分的合適位置，最終得到排序的序列。

代碼實現(xiàn)：

// 直接插入排序
void InsertionSort(vector<int> &num) {
    int len = num.size();
    for (int i = 1; i < len; ++i) {
        int tmp = num[i];
        int j = i - 1;
        while (j >= 0 && num[j] > tmp) {
            num[j + 1] = num[j];
            --j;
        }

        num[j + 1] = tmp;
    }
}

算法分析：

• 時間復雜度：$O(n^2)$

• 空間復雜度：$O(1)$

• 穩(wěn)定性：穩(wěn)定排序

3. 冒泡排序（Bubble Sort）

基本思想：

把第一個元素與第二個元素比較，如果第一個比第二個大，則交換他們的位置。接著繼續(xù)比較第二個與第三個元素，如果第二個比第三個大，則交換他們的位置……對每一對相鄰元素執(zhí)行同樣操作，一趟比較完成后，排在最右的元素便是最大的數(shù)。除去最右的元素，對剩余的元素做同樣的工作，最終得到排序序列。

代碼實現(xiàn)：

// 冒泡排序
void BubbleSort(vector<int> &num) {
    int len = num.size();
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < len - i - 1; ++j) {
            if (num[j + 1] < num[j])
                mySwap(num[j + 1], num[j]);
        }
    }
}

算法分析：

• 時間復雜度：$O(n^2)$

• 空間復雜度：$O(1)$

• 穩(wěn)定性：穩(wěn)定排序

算法優(yōu)化：

假如從開始的第一對到結(jié)尾的最后一對，相鄰的元素之間都沒有發(fā)生交換的操作，這意味著右邊的元素總是大于等于左邊的元素，此時的數(shù)組已經(jīng)是有序的了，無需再對剩余的元素重復比較下去了。

// 冒泡排序優(yōu)化
void BubbleSortPlus(vector<int> &num) {
    int len = num.size();
    for (int i = 0; i < len; ++i) {
        bool flag = true;
        for (int j = 0; j < len - i - 1; ++j) {
            if (num[j + 1] < num[j]) {
                mySwap(num[j + 1], num[j]);
                flag = false;
            }
        }
        if (flag)
            break;
    }
}

4. 希爾排序（Shell Sort）

基本思想：

希爾排序可以說是插入排序的一種變種。無論是插入排序還是冒泡排序，如果數(shù)組的最大值剛好是在第一位，要將它挪到正確的位置就需要 n - 1 次移動。也就是說，原數(shù)組的一個元素如果距離它正確的位置很遠的話，則需要與相鄰元素交換很多次才能到達正確的位置，這樣是相對比較花時間了。

希爾排序就是為了加快速度簡單地改進了插入排序，交換不相鄰的元素以對數(shù)組的局部進行排序。先讓數(shù)組中任意間隔為 h 的元素有序，剛開始 h 的大小可以是 h = n / 2,接著讓 h = n / 4，讓 h 一直縮小，當 h = 1 時，也就是此時數(shù)組中任意間隔為1的元素有序，此時的數(shù)組就是有序的了。

代碼實現(xiàn)：

// 希爾排序
void ShellSort(vector<int> &num) {
    int len = num.size();

    // 逐漸縮小間隔，最終為1
    for (int step = len / 2; step > 0; step /= 2) {   
        for (int i = step; i < len; ++i) {
            int tmp = num[i];
            int j = i - step;
            while (j >= 0 && tmp < num[j]) {
                num[j + step] = num[j];
                j -= step;
            }
            num[j + step] = tmp;
        }
    }
}

算法分析：

• 時間復雜度：$O(n^2)$

• 空間復雜度：$O(1)$

• 穩(wěn)定性：不穩(wěn)定排序

5. 歸并排序（Merge Sort）

基本思想：

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是分治法（Divide and Conquer）的典型應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

根據(jù)具體的實現(xiàn)，歸并排序包括"從上往下"和"從下往上"2種方式。

1. 從下往上（循環(huán)）：將待排序的數(shù)列分成若干個長度為1的子數(shù)列，然后將這些數(shù)列兩兩合并；得到若干個長度為2的有序數(shù)列，再將這些數(shù)列兩兩合并；得到若干個長度為4的有序數(shù)列，再將它們兩兩合并；直到合并成一個數(shù)列為止。這樣就得到了最終的排序結(jié)果。

2. 從上往下（遞歸）：它基本包括3步：

   • 分解：將當前區(qū)間一分為二，即求分裂點 mid = (low + high) / 2；
   • 求解：遞歸地對兩個子區(qū)間 [low…mid] 和 [mid+1…h(huán)igh] 進行歸并排序。遞歸的終結(jié)條件是子區(qū)間長度為1；
   • 合并：將已排序的兩個子區(qū)間 [low…mid] 和 [mid+1…h(huán)igh] 歸并為一個有序的區(qū)間 [low…h(huán)igh]。

5.1 非遞歸（循環(huán)）式歸并

代碼實現(xiàn)：

// 合并兩個有序數(shù)組
void Merge(vector<int> &num, int left, int mid, int right) {
    vector<int> leftSubArray(num.begin() + left, num.begin() + mid + 1);
    vector<int> rightSubArray(num.begin() + mid + 1, num.begin() + right + 1);

    int idxLeft = 0, idxRight = 0;
    // 在數(shù)組最后插入int類型能表示的最大值
    leftSubArray.insert(leftSubArray.end(), numeric_limits<int>::max());
    rightSubArray.insert(rightSubArray.end(), numeric_limits<int>::max());
   
    // 已有元素不可能大于int能表示的最大值，因此能覆蓋兩個數(shù)組中的所有元素
    for (int i = left; i <= right; i++) {
        if (leftSubArray[idxLeft] < rightSubArray[idxRight]) {
            num[i] = leftSubArray[idxLeft];
            idxLeft++;
        } else {
            num[i] = rightSubArray[idxRight];
            idxRight++;
        }
    }
}

// 歸并排序——非遞歸
void MergeSortLoop(vector<int> &num) {
    int len = num.size();
    // 子數(shù)組的大小分別為1，2，4，8...
    for (int i = 1; i < len; i += i) {
        // 進行數(shù)組劃分
        int left = 0;
        int mid = left + i - 1;
        int right = mid + i;
        // 將數(shù)組大小為 i 的數(shù)組兩兩合并
        while (right < len) {
            Merge(num, left, mid, right);
            left = right + 1;
            mid = left + i - 1;
            right = mid + i;
        }
        // 還有一些被遺漏的數(shù)組沒合并，因為不可能每個子數(shù)組的大小都剛好為 i
        if (left < len && mid < len) {
            Merge(num, left, mid, len - 1);
        }
    }
}

5.2 遞歸式歸并

代碼實現(xiàn)：

// 歸并排序——遞歸
void MergeSortRecursion(vector<int> &num, int left, int right) {
    if (left >= right)
        return;
    
    int mid = (right - left) / 2 + left;
    MergeSortRecursion(num, left, mid);
    MergeSortRecursion(num, mid + 1, right);
    Merge(num, left, mid, right);
}

算法分析：

• 時間復雜度：$O(n?logn)$

• 空間復雜度：$O(n)$

• 穩(wěn)定性：穩(wěn)定排序

6. 快速排序（Quick Sort）

基本思想：

從數(shù)組中選擇一個元素，稱為中軸元素。把數(shù)組中所有小于中軸元素的元素放在其左邊，所有大于或等于中軸元素的元素放在其右邊，顯然，此時中軸元素所處的位置的是有序的。也就是說，我們無需再移動中軸元素的位置。

以中軸元素為界把大的數(shù)組切割成兩個小的數(shù)組（分割操作，partition），且兩個數(shù)組都不包含中軸元素。對中軸元素左右兩邊的數(shù)組進行遞歸操作，直到數(shù)組的大小為1。此時每個元素都處于有序的位置。

代碼實現(xiàn)：

// 分割操作
int Partition(vector<int> &num, int left, int right) {
    int pivot = num[left];
    int i = left + 1, j = right;
   
    while (true) {
        // 向右找到第一個小于等于 pivot 的元素位置
        while (i <= j && num[i] <= pivot) 
            ++i;
        // 向左找到第一個大于等于 pivot 的元素位置
        while(i <= j && num[j] >= pivot ) 
            --j;
        
        if(i >= j)
            break;

        // 交換兩個元素的位置，使得左邊的元素不大于pivot,右邊的不小于pivot
        mySwap(num[i], num[j]);
    }
    // 使中軸元素處于有序的位置
    num[left] = num[j];  
    num[j] = pivot;
    
    return j;
}

// 另一種分割操作，參考《劍指Offer2》
int Partition2(vector<int> &num, int left, int right) {
    // 快排時間復雜度與中軸元素的選擇有關(guān)
    int index = RandomInRange(left, right);
    // 隨機選擇中軸元素
    mySwap(num[index], num[end]);
    
    int small = left - 1;
    for (int i = left; i < right; ++i) {
        if (num[i] < num[right]) {
            ++small;
            if (small != i)
                mySwap(num[i], num[small]);
        }
    }

    ++small;
    mySwap(num[small], num[right]);

    return small;
}

// 快速排序
void QuickSort(vector<int> &num, int left, int right) {
    if (left < right) {
        // 獲取中軸元素所處的位置并進行分割
        int mid = Partition(num, left, right);
        
        // 遞歸處理
        QuickSort(num, left, mid - 1);
        QuickSort(num, mid + 1, right);
    }
}

算法分析：

• 時間復雜度：$O(n?logn)$

• 空間復雜度：$O(logn)$

• 穩(wěn)定性：不穩(wěn)定排序

7. 堆排序（Heap Sort）

基本思想：

堆的特點就是堆頂?shù)脑厥且粋€最值，大頂堆的堆頂是最大值，小頂堆則是最小值。

堆排序就是把堆頂?shù)脑嘏c最后一個元素交換，交換之后破壞了堆的特性，我們再把堆中剩余的元素再次構(gòu)成一個大頂堆，然后再把堆頂元素與最后第二個元素交換….如此往復下去，等到剩余的元素只有一個的時候，此時的數(shù)組就是有序的了。

代碼實現(xiàn)：

// 下沉操作
void downAdjust(vector<int> &num, int parent, int n) {  
    // 臨時保存要下沉的元素  
    int temp = num[parent];      
    // 定位左孩子節(jié)點的位置
    int child = 2 * parent + 1;    
    
    // 開始下沉
    while (child <= n) {
        // 如果右孩子節(jié)點比左孩子大，則定位到右孩子
        if (child + 1 <= n && num[child] < num[child + 1])
            ++child;
        
        // 如果孩子節(jié)點小于或等于父節(jié)點，則下沉結(jié)束
        if (num[child] <= temp) 
            break;
        
        // 父節(jié)點進行下沉
        num[parent] = num[child];
        parent = child;
        child = 2 * parent + 1;
    }
    num[parent] = temp;
}

// 堆排序
void HeapSort(vector<int> &num) {
    int len = num.size();
    
    // 構(gòu)建大頂堆
    for (int i = (len - 2) / 2; i >= 0; --i) {
        downAdjust(num, i, len - 1);
    }
    
    // 進行堆排序
    for (int i = len - 1; i >= 1; --i) {
        // 把堆頂元素與最后一個元素交換
        mySwap(num[0], num[i]);
        // 把打亂的堆進行調(diào)整，恢復堆的特性
        downAdjust(num, 0, i - 1);
    }
}

算法分析：

• 時間復雜度：$O(n?logn)$

• 空間復雜度：$O(1)$

• 穩(wěn)定性：不穩(wěn)定排序

8. 計數(shù)排序（Counting Sort）

基本思想：

計數(shù)排序適合于最大值和最小值的差值不是很大的情況。

把數(shù)組元素作為數(shù)組的下標，然后用一個臨時數(shù)組統(tǒng)計該元素出現(xiàn)的次數(shù)，例如 temp[i] = m, 表示元素 i 一共出現(xiàn)了 m 次。最后再把臨時數(shù)組統(tǒng)計的數(shù)據(jù)從小到大匯總起來，此時匯總起來是數(shù)據(jù)是有序的。

代碼實現(xiàn)：

// 計數(shù)排序
void CountingSort(vector<int> &num) { 
    int len = num.size();
    
    // 得到數(shù)列的最大和最小值
    int max = num[0], min = num[0];  
    for (int i = 1; i < len; ++i) {        
        if(num[i] > max)           
            max = num[i];        
        
        if (num[i] < min)
            min = num[i];
    }
    
    // 根據(jù)數(shù)列最大值確定統(tǒng)計數(shù)組的長度
    vector<int> countArray(max - min + 1, 0);
    
    // 遍歷數(shù)列，填充統(tǒng)計數(shù)組
    for (int i = 0; i < len; ++i) {
        countArray[num[i] - min]++;
    }
    
    // 遍歷統(tǒng)計數(shù)組，輸出結(jié)果   
    int index = 0;  
    for (int i = 0; i < countArray.size(); ++i) {
        for (int j = 0; j < countArray[i]; ++j) {
            num[index++] = i + min;
        }
    }  
}

算法分析：

• 時間復雜度：$O(n+k)$，其中k為臨時數(shù)組大小

• 空間復雜度：$O(k)$

• 穩(wěn)定性：穩(wěn)定排序

9. 桶排序（Bucket Sort）

基本思想：

桶排序就是把最大值和最小值之間的數(shù)進行瓜分，例如分成 10 個區(qū)間，10個區(qū)間對應10個桶，我們把各元素放到對應區(qū)間的桶中去，再對每個桶中的數(shù)進行排序，可以采用歸并排序、快速排序等方法。之后每個桶里面的數(shù)據(jù)就是有序的了，按順序遍歷各桶即可得到排序序列。桶排序也可用于浮點數(shù)排序。

代碼實現(xiàn)：

// 桶排序
// 有負數(shù)的話需要進行預處理，本函數(shù)包含預處理部分
void BucketSort(vector<int> &num) {   
    int len = num.size();
    
    // 得到數(shù)列的最大最小值
    int max = num[0], min = num[0];  
    for(int i = 1; i < len; ++i) {        
        if(num[i] > max)           
            max = num[i];        
        
        if (num[i] < min)
            min = num[i];
    }
    
    // 計算桶的數(shù)量并初始化
    int bucketNum = (max - min) / len + 1;
    vector<int> vec;
    vector<vector<int>> bucket;
    for (int i = 0; i < bucketNum; ++i)
        bucket.push_back(vec);
    
    // 將每個元素放入桶
    for (int i = 0; i < len; ++i) {
        // 減去最小值，處理后均為非負數(shù)
        int pos = (num[i] - min) / len;
        bucket[pos].push_back(num[i]);
    }
    
    // 對每個桶進行排序，此處可選擇不同排序方法
    for (int i = 0; i < bucket.size(); ++i) 
        sort(bucket[i].begin(), bucket[i].end());
    
    // 將桶中的元素賦值到原序列
	int index = 0;
	for (int i = 0; i < bucketNum; ++i)
		for(int j = 0; j < bucket[i].size(); ++j)
			num[index++] = bucket[i][j];
}

算法分析：

• 時間復雜度：$O(n+k)$

• 空間復雜度：$O(k)$

• 穩(wěn)定性：穩(wěn)定排序

10. 基數(shù)排序（Radix Sort）

基本思想：

先以個位數(shù)的大小來對數(shù)據(jù)進行排序，接著以十位數(shù)的大小來多數(shù)進行排序，接著以百位數(shù)的大小……

排到最后，就是一組有序的元素了。在以某位數(shù)進行排序的時候，是用“桶”來排序的。

由于某位數(shù)（個位/十位….，不是一整個數(shù)）的大小范圍為0~9，所以我們需要10個桶，然后把具有相同數(shù)值的數(shù)放進同一個桶里，之后再把桶里的數(shù)按照0號桶到9號桶的順序取出來。一趟下來按照某位數(shù)的排序就完成了。

代碼實現(xiàn)：

// 基數(shù)排序
// 有負數(shù)的話需要進行預處理，本函數(shù)不包含預處理部分
void RadixSort(vector<int> &num) {
    int len = num.size();
    
    // 得到數(shù)列的最大值
    int max = num[0];  
    for (int i = 1; i < len; ++i) {        
        if(num[i] > max)           
            max = num[i];
    }

    // 計算最大值是幾位數(shù)
    int times = 1;
    while (max / 10 > 0) {
        ++times;
        max /= 10;
    }

     // 創(chuàng)建10個桶
    vector<int> vec;
    vector<vector<int>> bucket;
    for (int i = 0; i < 10; ++i) {
        bucket.push_back(vec);
    }
    
    // 進行每一趟的排序，從個位數(shù)開始排
    for (int i = 1; i <= times; i++) {
        for (int j = 0; j < len; j++) {
            // 獲取每個數(shù)最后第 i 位對應桶的位置
            int radio = (num[j] / (int)pow(10,i-1)) % 10;
            // 放進對應的桶里
            bucket[radio].push_back(num[j]);
        }
        // 合并放回原數(shù)組
        int k = 0;
        for (int j = 0; j < 10; j++) {
            for (int& t : bucket[j]) {
                num[k++] = t;
            }
            //合并之后清空桶
            bucket[j].clear();
        }  
    }
}

算法分析：

• 時間復雜度：$O(k?n)$

• 空間復雜度：$O(k+n)$

• 穩(wěn)定性：穩(wěn)定排序

11. 總結(jié)

文章來源地址http://www.zghlxwxcb.cn/news/detail-480043.html

參考資料

• 10 Best Sorting Algorithms You Must Know About
• 必學十大經(jīng)典排序算法
• 歸并排序（Merge Sort）
• 二叉堆是什么鬼？
• 為什么說O(n)復雜度的基數(shù)排序沒有快速排序快？

到了這里，關(guān)于十大排序算法（Top 10 Sorting Algorithms）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！