高级排序算法实现与优化

// 将 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);
}

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));
            }
        }
    }
}

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);
}

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);
}

#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);
// ...