高級排序演算法實現與優化_ZenDei技術網路在線

本文用到的測試數據生成的代碼和分析： "《測試數據自動生成》" 文章圖片來源於 GitHub，網速不佳的朋友 "請點我看原文" 。順便軟廣一下個人技術小站： "godbmw.com" 。歡迎常來 ♪\(^∇^\ \) 1. 談談高級排序本文主要介紹高級排序演算法中的歸併排序和快速排序。他們有運用了 ...

本文用到的測試數據生成的代碼和分析：《測試數據自動生成》

文章圖片來源於 GitHub，網速不佳的朋友請點我看原文。

順便軟廣一下個人技術小站：godbmw.com。歡迎常來 ♪(^∇^*)

1. 談談高級排序

本文主要介紹高級排序演算法中的歸併排序和快速排序。他們有運用了分支思想，並且大多通過遞歸來實現。

對於歸併排序，分為自上向底和自底向上排序。對於快速排序，有常見的二路快排和系統級常用的三路快速排序。

2. 歸併排序

2.1 設計和分析

在演算法思想上：歸併排序是分治法，所以需要等分數組，並且逐個完成排序，然後再合併在一起。而因為等分，所以樹結構是平衡的（快速排序就不一定，需要進一步優化）。

在空間使用上：歸併排序需要開啟輔助空間，所以，在演算法效率上自然比不上快速排序。

2.2 自頂向下的歸併

2.2.1 三處優化

第一處優化是關於選取中間索引值的問題。顯然，使用(l + r) / 2可能會造成溢出。

所以，此處應該是：int mid = l + (r - l) / 2;。

同時，不能是 r + (l - r) / 2 。比如: l = 0, r = 1 的時候，這條式子的結果和(l + r) / 2不同。因為 c++的自動向下取整。

第二處優化是關於遞歸到底層的時候，比如被切分出來的數據長度小於 15，此時可以使用插入排序來優化。

第三處優化是當歸併前，先判斷前一部分數據的最後一個值和後一部分數據最後一個值的大小關係，再決定是否優化。

2.2.2 代碼實現

實現中比較困難的部分是歸併過程，在處理邊界的時候，需要特別註意。示意圖如下：

// 將 arr[l, ... , mid] 和 arr[mid, ... , r]兩個部分進行歸併
template <typename T>
void __merge(T arr[], int l, int mid, int r) {
    T* aux = new T[r - l + 1]; // 輔助空間
    for(int i = l; i<=r; i++) {
        aux[i - l] = arr[i];
    }
    int i = l, j = mid + 1;
    for(int k = l; k <= r; k++) {
        if( i > mid) {
            arr[k] = aux[j - l];
            j++;
        } else if (j > r) {
            arr[k] = aux[i - l];
            i++;
        } else if(aux[i - l] < aux[j - l]) {
            arr[k] = aux[i - l];
            i++;
        } else {
            arr[k] = aux[j - l];
            j++;
        }
    }
    delete[] aux;
}

// 遞歸使用歸併排序, 對arr[l, ... , r]的範圍的數據進行排序
template <typename T>
void __mergeSort(T arr[], int l, int r) {
    // 遞歸到底層的情況
    if( r - l <= 15 ){
        SortBase::insertionSort(arr, l, r);
        return;
    }

    int mid = l + (r - l)/2;

    // 防止溢出：同時，不能是 r + (l - r) / 2 。 比如: l = 0, r = 1

    __mergeSort(arr, l, mid);
    __mergeSort(arr, mid + 1, r);
    if(arr[mid] > arr[mid + 1]) {
        __merge(arr, l, mid, r);
    }
}

template <typename T>
void mergeSort(T arr[], int n) {
    __mergeSort(arr, 0, n-1);
}

2.3 自底向上的歸併

自底向上的歸併排序不如自頂向下的歸併好理解。但是可以不寫遞歸函數，並且可以訪問數組索引。

有道面試題：對於一個鏈表（每個節點存儲一個數據），要求在 O(NlogN)時間內完成排序，並且使用常數級別的空間。利用的就是

先看自底向上的歸併的實現，就會有思路了：

template <typename T>
void mergeSortBU(T arr[], int n) {
    int min_size = -1;
    for(int sz = 1; sz <= n; sz += sz) {
        for(int i = 0; i + sz < n; i += sz + sz) { // i + sz < n: 保證第二部分的數組存在，並且 i + sz -1 不越界
//                 對 arr[i, ... ,i+sz-1] 和 [i+sz, ... ,i+2*sz-1] 進行歸併
            if(arr[i + sz - 1] > arr[i + sz]) {
                __merge(arr, i, i + sz -1, min(i + sz + sz -1, n-1));
            }
        }
    }
}

這段代碼是針對數組的，如果針對鏈表，只需要移動指針即可，而空間也可以新開一個指針空間做原地操作。>>>請看這篇博文

3. 快速排序

3.1 二路快速排序

3.1.1 三處優化

第一處優化是關於遞歸到底層的時候，比如被切分出來的數據長度小於 15，此時可以使用插入排序來優化。

第二處優化是：隨機選擇標定元素。一般的快排選定的是最左邊的元素作為標定元素，排序後的數組標定元素移動到應該所處的位置，其前面是比他小的元素，後面是比他大的元素。

然而，無法保證快速排序遞歸樹的平衡度。比如：2, 2, 2,..., 2, 1 近乎有序且有大量重覆的數組。如果選定最左邊，快速排序就會退化到 O(N*N)。如下圖所示：

優化方法是：隨機選擇一個元素，與第一個元素交換後作為標定元素。這樣可以保證遞歸樹深度的期望值是 logN。

第三處優化是針對數組中有大量重覆元素的情況。在執行partition操作的時候，判斷是否移動交換元素的條件算上=即可。（具體可以看之後代碼）

3.1.2 代碼實現

template <typename T>
int __partition2(T arr[], int l, int r) {
    swap(arr[l], arr[rand()%(r - l + 1) + l]); // 隨機化防止樹不平衡
    T v = arr[l];

//        arr[l+1, ... , i) <= v; arr(j, ... , r] >= v
    int i = l + 1, j = r;
    while(true) {
        while(i <= r && arr[i] < v) i++;
        while(j >= l+1 && arr[j] > v) j--;
        if(i > j) break;
        swap(arr[i], arr[j]);
        i ++;
        j --;
    }
    swap(arr[l], arr[j]);

    return j;
}


template <typename T>
void __quickSort(T arr[], int l, int r) {
    if(r - l <= 15) {
        SortBase::insertionSort(arr, l, r);
        return;
    }
    int p = __partition2(arr, l, r);
    __quickSort(arr, l, p-1);
    __quickSort(arr, p+1, r);
}

template <typename T>
void quickSort(T arr[] ,int n) {
    srand(time(NULL));
    __quickSort(arr, 0, n-1);
}

3.2 三路快速排序

三路排序和二路不同的是：將相同的元素單獨放在一起，每次遞歸不再參與排序。

代碼中各個邊界變數的含義如下圖所示：

代碼實現：

template <typename T>
void __quickSort3Ways(T arr[], int l, int r) {
    if(r - l <= 15) {
        SortBase::insertionSort(arr, l, r);
        return;
    }

    swap(arr[l], arr[rand() % (r - l + 1) + l]);
    T v = arr[l];

    int lt = l; // arr[l + 1, ... , lt] < v
    int gt = r + 1; // arr[gt, ... ,r] > v
    int i = l + 1; // arr[lt + 1, ... , i) == v
    while( i < gt ) {
        if(arr[i] < v) {
            swap(arr[i], arr[lt + 1]);
            lt ++;
            i ++;
        } else if(arr[i] > v) {
            swap(arr[i], arr[gt - 1]);
            gt --;
        } else {
            i ++;
        }
    }
    swap(arr[l], arr[lt]);
    __quickSort3Ways(arr, l, lt-1);
    __quickSort3Ways(arr, gt, r);
}

4. 性能測試

4.1 測試隨機數據

為了保證普適性，先測試大量隨機數據的演算法表現：

#include <iostream>
#include "SortHelper.h"
#include "SortBase.h"
#include "SortAdvance.h"

using namespace std;

int main() {
    int n = 100000, left = 0, right = n;
    int *arr = SortTestHelper::generateRandomArray<int>(n, left, 5);
    int *brr = SortTestHelper::copyArray<int>(arr, n);
    int *crr = SortTestHelper::copyArray<int>(arr, n);
    int *drr = SortTestHelper::copyArray<int>(arr, n);

    SortTestHelper::testSort<int>(brr, n, SortAdvance::mergeSort<int>, "merge sort");
    SortTestHelper::testSort<int>(crr, n, SortAdvance::mergeSortBU<int>, "merge sort from bottom to up");
    SortTestHelper::testSort<int>(drr, n, SortAdvance::quickSort<int>, "quick sort");
    return 0;
}

結果如下：

對於特殊數據，例如含有大量重覆元素的數組：

// ...
int *arr = SortTestHelper::generateRandomArray<int>(n, left, 5);
// ...

結果如下圖所示：

4.2 1 億數據量測試

因為使用的 CLion 做了安全限制，所以當數組大小開到 100w 的時候，就報出堆棧錯誤。

換用了 DevC 來跑 1 億的數據，快排本來是 17s（忘記截圖了），再跑就是 27s，如下圖所示：

大家可以在自己電腦跑一下百度百科的快排，就知道優化的作用了 :)

5. 感謝

本篇博客是總結於慕課網的《學習演算法思想修煉編程內功》的筆記，liuyubobobo 老師人和講課都很 nice，歡迎去買他的課程。