main.cpp

#include <iostream>
#include "SortTestHelper.h"
#include "SortAlgorithm.h"

int main() {
    /* 100万个数据的排序结果

    对一个随机数组进行排序
    Shell Sort: :51.5798s
    Merge Sort: :0.231673s
    QuickSort Sort: :0.255111s
    2 Ways Quick Sort: :0.181188s
    3 Ways Quick Sort: :0.303083s

    对近乎有序的数组进行排序
    Shell Sort: :0.122397s
    Merge Sort: :0.065564s
    QuickSort Sort: :0.179152s
    2 Ways Quick Sort: :0.069877s
    3 Ways Quick Sort: :0.229419s

    对存在大量重复元素的数组进行排序
    Shell Sort: :51.1946s
    Merge Sort: :0.179235s
    QuickSort Sort: :11.8389s
    2 Ways Quick Sort: :0.121224s
    3 Ways Quick Sort: :0.086746s*/

    int n = 1000000;
    cout<<"对一个随机数组进行排序"<<endl;
    int *arr = SortTestHelper::generateRandomArray(n, 0, 10*n);
    int *arrCopy1 = SortTestHelper::copyIntArr(arr, n);
    int *arrCopy2 = SortTestHelper::copyIntArr(arr, n);
    int *arrCopy3 = SortTestHelper::copyIntArr(arr, n);
    int *arrCopy4 = SortTestHelper::copyIntArr(arr, n);
    int *arrCopy5 = SortTestHelper::copyIntArr(arr, n);
    int *arrCopy6 = SortTestHelper::copyIntArr(arr, n);
    int *arrCopy7 = SortTestHelper::copyIntArr(arr, n);
//    SortTestHelper::testSort("Bubble Sort: ", On2::bubbleSort, arr, n);
//    SortTestHelper::testSort("Selection Sort: ", On2::selectionSort, arrCopy1, n);
//    SortTestHelper::testSort("Insert Sort: ", On2::insertSortV2, arrCopy2, n);
    SortTestHelper::testSort("Shell Sort: ", On2::shellSort, arrCopy3, n);
    SortTestHelper::testSort("Merge Sort: ", Onlogn::MergeSort::mergeSort, arrCopy4, n);
    SortTestHelper::testSort("QuickSort Sort: ", Onlogn::QuickSortV1_2::quickSort, arrCopy5, n);
    SortTestHelper::testSort("2 Ways Quick Sort: ", Onlogn::QuickSort2ways::quickSort2Ways, arrCopy6, n);
    SortTestHelper::testSort("3 Ways Quick Sort: ", Onlogn::QuickSort3Ways::quickSort3Ways, arrCopy7, n);

    cout<<endl;
    cout<<"对近乎有序的数组进行排序"<<endl;
    int *arrOrdered = SortTestHelper::generateNearlyOrderedArray(n, 100);
    int *arrOrderedCopy1 = SortTestHelper::copyIntArr(arrOrdered, n);
    int *arrOrderedCopy2 = SortTestHelper::copyIntArr(arrOrdered, n);
    int *arrOrderedCopy3 = SortTestHelper::copyIntArr(arrOrdered, n);
    int *arrOrderedCopy4 = SortTestHelper::copyIntArr(arrOrdered, n);
    int *arrOrderedCopy5 = SortTestHelper::copyIntArr(arrOrdered, n);
    int *arrOrderedCopy6 = SortTestHelper::copyIntArr(arrOrdered, n);
    int *arrOrderedCopy7 = SortTestHelper::copyIntArr(arrOrdered, n);
//    SortTestHelper::testSort("Bubble Sort: ", On2::bubbleSort, arrOrdered, n);
//    SortTestHelper::testSort("Selection Sort: ", On2::selectionSort, arrOrderedCopy1, n);
//    SortTestHelper::testSort("Insert Sort: ", On2::insertSortV2, arrOrderedCopy2, n);
    SortTestHelper::testSort("Shell Sort: ", On2::shellSort, arrOrderedCopy3, n);
    SortTestHelper::testSort("Merge Sort: ", Onlogn::MergeSort::mergeSort, arrOrderedCopy4, n);
    SortTestHelper::testSort("QuickSort Sort: ", Onlogn::QuickSortV1_2::quickSort, arrOrderedCopy5, n);
    SortTestHelper::testSort("2 Ways Quick Sort: ", Onlogn::QuickSort2ways::quickSort2Ways, arrOrderedCopy6, n);
    SortTestHelper::testSort("3 Ways Quick Sort: ", Onlogn::QuickSort3Ways::quickSort3Ways, arrOrderedCopy7, n);

    cout<<endl;
    cout<<"对存在大量重复元素的数组进行排序"<<endl;
    int *arrDup = SortTestHelper::generateRandomArray(n, 0, 100);
    int *arrDupCopy1 = SortTestHelper::copyIntArr(arrDup, n);
    int *arrDupCopy2 = SortTestHelper::copyIntArr(arrDup, n);
    int *arrDupCopy3 = SortTestHelper::copyIntArr(arrDup, n);
    int *arrDupCopy4 = SortTestHelper::copyIntArr(arrDup, n);
    int *arrDupCopy5 = SortTestHelper::copyIntArr(arrDup, n);
    int *arrDupCopy6 = SortTestHelper::copyIntArr(arrDup, n);
    int *arrDupCopy7 = SortTestHelper::copyIntArr(arrDup, n);
//    SortTestHelper::testSort("Bubble Sort: ", On2::bubbleSort, arrDup, n);
//    SortTestHelper::testSort("Selection Sort: ", On2::selectionSort, arrDupCopy1, n);
//    SortTestHelper::testSort("Insert Sort: ", On2::insertSortV2, arrDupCopy2, n);
    SortTestHelper::testSort("Shell Sort: ", On2::shellSort, arrDupCopy3, n);
    SortTestHelper::testSort("Merge Sort: ", Onlogn::MergeSort::mergeSort, arrDupCopy4, n);
    SortTestHelper::testSort("QuickSort Sort: ", Onlogn::QuickSortV1_2::quickSort, arrDupCopy5, n);
    SortTestHelper::testSort("2 Ways Quick Sort: ", Onlogn::QuickSort2ways::quickSort2Ways, arrDupCopy6, n);
    SortTestHelper::testSort("3 Ways Quick Sort: ", Onlogn::QuickSort3Ways::quickSort3Ways, arrDupCopy7, n);


    //释放空间
    delete [] arr;
    delete [] arrCopy1;
    delete [] arrCopy2;
    delete [] arrCopy3;
    delete [] arrCopy4;
    delete [] arrCopy5;
    delete [] arrCopy6;
    delete [] arrCopy7;

    delete [] arrOrdered;
    delete [] arrOrderedCopy1;
    delete [] arrOrderedCopy2;
    delete [] arrOrderedCopy3;
    delete [] arrOrderedCopy4;
    delete [] arrOrderedCopy5;
    delete [] arrOrderedCopy6;
    delete [] arrOrderedCopy7;

    delete [] arrDup;
    delete [] arrDupCopy1;
    delete [] arrDupCopy2;
    delete [] arrDupCopy3;
    delete [] arrDupCopy4;
    delete [] arrDupCopy5;
    delete [] arrDupCopy6;
    delete [] arrDupCopy7;
}

SortTestHelper.h

#ifndef SELECTIONSORT_SORTTESTHELPER_H
#define SELECTIONSORT_SORTTESTHELPER_H

#include <iostream>
#include <ctime>
#include <cassert>
using namespace std;

namespace SortTestHelper{

    //返回一个在[rangeL,rangeR]范围内元素数量为n的随机整形数组
    int* generateRandomArray(int n, int rangeL, int rangeR){

        assert(rangeL < rangeR);
        int* arr = new int[n];
        srand(time(NULL)); //设置随机种子
        for (int i = 0; i < n; ++i) {
           arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
        }
        return arr;
    }

    template <typename T>
    void printArray(T arr ,int n){
        for(int i = 0; i < n; i++){
            cout << arr[i] << " ";
        }
        cout << endl;
    }

    template <typename T>
    bool isSorted(T arr, int n, const string sortName){
        for (int i = 0; i < n - 1; ++i) {
            if(arr[i]>arr[i+1]){
                cout << "sort failed: " << sortName << ".";
                return false;
            }
        }
        return true;
    }

    template <typename T>
    void testSort(const string &sortName, void(*sort)(T[], int n), T arr[], int n){
        clock_t startTime = clock();
        sort(arr,n);
        clock_t endTime = clock();

        assert(isSorted(arr,n,sortName));

        cout << sortName << ":" <<(float)(endTime-startTime)/CLOCKS_PER_SEC << "s" <<endl;
    }

    int* copyIntArr(int arr[], int n){

        int* array = new int[n];
        copy(arr,arr+n,array);
        return array;
    }

    int* generateNearlyOrderedArray(int n, int swapTimes){
        int* arr = new int[n];
        for(int i = 0 ; i < n ; i++){
            arr[i] = i;
        }
        srand(time(NULL));
        for (int i = 0 ; i < swapTimes ; i++){
            int index0 = rand()%n;
            int index1 = rand()%n;
            swap( arr[index0] , arr[index1] );
        }
        return arr;
    }

    template <typename T>
    int getArrLength(T& arr){
        //T& arr是对变量的引用，而不是取地址(取地址是& arr，没有前面的类型声明)。
        //通过T& arr引用变量实际上是给实参变量取了一个叫做arr的别名。在内部使用arr就是对实参变量的操作。
        //这是C++对C的一个补充用法。
        return sizeof(arr)/ sizeof(arr[0]);

    }


}
#endif //SELECTIONSORT_SORTTESTHELPER_H

SortAlgorithm.h

#ifndef INSERTSORT_SELECTIONSORT_H
#define INSERTSORT_SELECTIONSORT_H

using namespace std;
namespace On2 {
    template<typename T>
    // 选择排序
    void selectionSort(T arr[], int n) {
        for (int i = 0; i < n; i++) {
            int minIndex = i;
            for (int j = minIndex; j < n; j++) {
                if (arr[j] < arr[minIndex])
                    minIndex = j;
            }
            swap(arr[i], arr[minIndex]);
        }
    }

    template<typename T>
    // 插入排序
    void insertSortV1(T arr[], int n) {
        for (int i = 1; i < n; ++i) {
            /*for (int cur = i; cur >0 ; --cur) {
                if(arr[cur]<arr[cur-1]){
                    swap(arr[cur],arr[cur-1]);
                }
                else break;*/
            // 以上的if条件可以简化到for循环中
            for (int cur = i; cur > 0 && arr[cur] < arr[cur - 1]; cur--) {
                swap(arr[cur], arr[cur - 1]);
            }
        }
    }


    template<typename T>
    // 优化后的插入排序，通过以赋值替换swap、提前终止遍历的方式，提高排序速度
    void insertSortV2(T arr[], int n) {
        for (int i = 1; i < n; ++i) {
            int min = arr[i];
            int j = i;
            for (; j > 0 && arr[j - 1] > min; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = min;
        }
    }

    template<typename T>
    // 插入排序。在其他O(nlogn)算法递归到数据量较少时，改用插入排序提高运行速率
    void insertSort(T arr[], int left, int right) {
        for (int i = left + 1; i <= right; ++i) {
            int min = arr[i];
            int j = i;
            for (; j > left && arr[j - 1] > min; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = min;
        }
    }

    template<typename T>
    //冒泡排序
    void bubbleSort(T arr[], int n) {
        // 每一轮依次对数组arr[0,i]的j和j+1位置进行比大小，若arr[j]>arr[j+1]则将arr[j]沉底
        for (int i = n - 1; i > 0; i--) {
            for (int j = 0; j < i; ++j) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr[j], arr[j + 1]);
                }
            }
        }

    }

    template<typename T>
    // 希尔排序的增量序列可选择Hibbard增量，即2^k-1，也可以选择质数序列。
    void shellSort(T arr[], int n) {
        // 对大小为n的数组执行希尔排序，处理的步长序列为[3,2,1]
        int step[] = {31, 29, 23, 19, 17, 13, 11, 9, 7, 5, 3, 2, 1};
        int stepLenth = sizeof(step) / sizeof(step[0]);
        for (int i = 0; i < stepLenth; i++) {
            // 对数组arr以步长step[i]切分子数组，在这些子数组上执行插入排序
            int initPos = 0;
            while (initPos < step[i]) {
                // 对子数组arr[initPos,initPos+step[i],initPos+2*step[i]...initPos+k*step]执行插入排序,其中initPos+k*step<n
                for (int x = initPos + step[i]; x < n; x += step[i]) {
                    int tmp = arr[x];
                    int y;
                    for (y = x; y > initPos; y -= step[i]) {
                        if (tmp < arr[y - step[i]])
                            arr[y] = arr[y - step[i]];
                        else
                            break;
                    }
                    arr[y] = tmp;
                }

                initPos++;
            }

        }
    }

}

namespace Onlogn {
    namespace QuickSortV1_1 {
        // 未进行任何优化的快速排序算法
        // 整理数组arr[left,right],使得所有位于[left,p-1]的元素都小于v，所有位于[p+1,right]的元素都大于v，
        // 其中v是arr[left,right]数组的第一个元素
        template<typename T>
        int __partition(T arr[], int left, int right) {
            int v = arr[left];
            int p = left;
            for (int i = p + 1; i <= right; i++) {
                if (arr[i] < v) {
                    swap(arr[p + 1], arr[i]);
                    p += 1;
                }
            }
            swap(arr[left], arr[p]);
            return p;
        }

        // 对arr[left,right]进行快速排序
        template<typename T>
        void __quickSort(T arr[], int left, int right) {
            if (left >= right)
                return;
            int p = __partition(arr, left, right);
            __quickSort(arr, left, p - 1);
            __quickSort(arr, p + 1, right);
        }

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


    namespace QuickSortV1_2 {
        // 优化后的快速排序
        // 将arr[l...r]进行partition操作
        // 返回pivot元素索引p，使得arr[l...p-1] < arr[p], 且arr[p+1...r] > arr[p]
        template<typename T>
        int __partition(T arr[], int l, int r) {
            // 将分为以下几个部分。
            // pivot点arr[l],arr[l+1....j]等小于pivot的元素，arr[j+1...i)等大于pivot的元素
            // 以及正在遍历的元素arr[i]，尚未遍历的部分arr[i+1...r]

            // 优化2.不再使用最左边的元素作为标定点，而是在数组中任选一个元素当做标定点，从而避免快排partition不均衡退化为O(n^2)算法
            srand(static_cast<unsigned int>(time(NULL)));
            swap(arr[l], arr[rand() % (r - l + 1) + l]);
            T v = arr[l];
            int j = l;
            for (int i = l + 1; i <= r; i++) {
                // 初始时，v为第一个元素arr[l]，正在遍历的元素为i
                // 小于元素v的区间[l+1...j]不存在，因为初始时j=l，l+1>j，区间变成了[l+1,l]。
                // 大于元素v的区间[j+1...i)不存在，因为初始时i=l+1，而l=j，区间变成了[j+1,j+1)。
                if (arr[i] < v) {
                    swap(arr[j + 1], arr[i]);
                    j++;
                }
            }
            swap(arr[l], arr[j]);
            return j;
        }

        // 对arr[left...right]进行快速排序
        template<typename T>
        void __quickSort(T arr[], int left, int right) {
            // 优化1.当剩余需要排序的数组元素数量低于一定数量时，使用插入排序进行处理
            if (right - left <= 10) {
                On2::insertSort(arr, left, right);
                return;
            }

            int p = __partition(arr, left, right);
            __quickSort(arr, left, p - 1);
            __quickSort(arr, p + 1, right);
        }

        template<typename T>
        void quickSort(T arr[], int n) {
            __quickSort(arr, 0, n - 1);
        }
    }
    namespace QuickSort2ways{
        // 双路快排
        // 对arr[l...r]进行双路partition操作，
        // 其中v表示pivot标定点元素，arr[i]表示当前遍历的元素，arr[j]为当前未遍历的最后一个元素
        // 通过partition整理数组，使得arr[l+1...i)<=arr[l],arr(j...r]>=arr[l]。
        // 若存在大量重复元素，由于i定义为第一个大于等于v的位置，j定义为第一个小于等于v的位置
        // partition后的效果为(e<v ... e=v,e=v,e=v...e>v),由于存在swap操作，因此partition后这些重复的元素会分别放在p的左右两侧
        // 这就避免了左右子区间元素数量出现倾斜，导致退化为O(n^2)的情况

        template <typename T>
        int __partition(T arr[], int l, int r){

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

            T v = arr[l];
            int i = l+1;
            int j = r;
            while(true){
                //i: 遍历时第一个使得arr[i]>=v的索引
                while (arr[i] < v && i<=r){
                    i++;
                }
                //j: 遍历时第一个使得arr[j]<=v的索引
                while (arr[j] > v && j>l){
                    j--;
                }
                if (i>j) break;
                swap(arr[i], arr[j]);
                i++;
                j--;
            }
            swap(arr[l] , arr[j]);
            return j;
        }


        // 对arr[l...r]进行双路快速排序
        template <typename T>
        void __quickSort(T arr[], int l, int r){
            if(r-l<=15){
                On2::insertSort(arr, l, r);
                return;
            }

            int p = __partition(arr, l, r);
            __quickSort(arr, l, p-1);
            __quickSort(arr, p+1, r);
        }

        // 对arr[0...n-1]进行双路快速排序
        template <typename T>
        void quickSort2Ways(T arr[], int n){
            srand(time(NULL));
            __quickSort(arr, 0, n-1);
        }
    }

    namespace QuickSort3Ways{
        //三路快排
        // 对arr数据进行三路快排操作
        // 使得arr[l+1...lt]<v, arr[lt+1...i-1]=v, arr[gt...r]>v
        // 其中lt表示当前循环中的最后一个小于v的元素的索引，gt表示第一个大于v的索引，
        // arr[i...gt-1]为尚未处理的元素，i为当前将要遍历的元素索引
        template <typename T>
        void __quickSort(T arr[], int l, int r){
            if (r-l <= 10){
                On2::insertSort(arr, l, r);
                return;
            }

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

            int lt = l;
            int gt = r+1;
            int i = l+1;

            while (i < gt){
                if(arr[i] < v){
                    swap(arr[i], arr[lt+1]);
                    i++;
                    lt++;
                }
                else if(arr[i] > v){
                    swap(arr[i], arr[gt-1]);
                    gt--;
                }
                else{ // arr[i] == v
                    i++;
                }
            }
            swap(arr[l], arr[lt]);
            lt -= 1; // 用于维护lt的定义：lt表示最后一个小于v的元素的索引

            // 递归处理
            __quickSort(arr, l, lt);
            __quickSort(arr, gt, r);
        }

        template <typename T>
        void quickSort3Ways(T arr[], int n){
            srand(time(NULL));
            __quickSort(arr, 0, n-1);
        }
    }
    namespace MergeSort {
        // 归并排序

        template<typename T>
        void __merge(T &arr, int left, int right) {
            // copy array
            int size = right - left + 1;
            int copyArr[size];
            for (int i = 0; i < size; i++) {
                copyArr[i] = arr[i + left];
            }

            // cur - 当前需要排序的位置
            // posI、posJ - 复制的数组中需要判断大小的位置
            int cur = left;
            int posI = 0;
            int posJ = (size - 1) / 2 + 1;
            while (cur <= right) {
                if ((copyArr[posJ] < copyArr[posI] && posJ < size) or (posI > (size - 1) / 2)) {
                    arr[cur] = copyArr[posJ];
                    posJ++;
                } else {
                    arr[cur] = copyArr[posI];
                    posI++;
                }
                cur++;
            }


        }

        template<typename T>
        void __mergeSort(T arr[], int left, int right) {
//             if (left == right)
//             return;
            if (right - left <= 8) { // 当剩余元素个数低于某个值时使用插入排序进行排序
                On2::insertSort(arr, left, right);
                return;
            }
            int mid = (right - left) / 2 + left;
            __mergeSort(arr, left, mid);
            __mergeSort(arr, mid + 1, right);
            if (arr[mid] > arr[mid + 1])
                __merge(arr, left, right);
        }

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

        }
    }

    namespace MergeSortBU {
        // MergeSortBotomToUp
        // 自底向上的归并排序，不再进行递归处理将数据分为一个个小区间
        // 而是将数据直接视作最底层，向上归并。
        template<typename T>
        void __merge(T arr[], int left, int mid, int right) {
            int size = right - left + 1;
            T arrCopy[size];
            for (int i = left; i <= right; i++) {
                arrCopy[i - left] = arr[i];
            }
            // 对arr[left,mid]和arr[mid+1,right]进行merge操作
            int l = 0;
            int r = mid - left + 1;
            for (int i = left; i <= right; ++i) {
                if (l > mid) {
                    arr[i] = arrCopy[r];
                    r++;
                } else if (r > size - 1) {
                    arr[i] = arrCopy[l];
                    l++;
                } else if (arrCopy[l] > arrCopy[r]) {
                    arr[i] = arrCopy[r];
                    r++;
                } else {
                    arr[i] = arrCopy[l];
                    l++;
                }
            }
        }

        template<typename T>
        void mergeSortBU(T arr[], int n) {
            // 对arr[i,i+sz-1]和arr[i+sz,i+2*zs-1]进行merge
            // i+sz<n保证了归并数组的右边部分有数据,i+2sz保证了每次跨过两个sz大小
            // 当右侧部分不足sz个元素时，将右侧全部元素(arr[i+sz,n-1])与左侧进行归并
            for (int sz = 1; sz <= n; sz += sz) {
                for (int i = 0; i + sz < n; i += 2 * sz) {
                    __merge(arr, i, i + sz - 1, min(i + 2 * sz - 1, n - 1));
                }
            }
        }
    }
}

#endif //INSERTSORT_SELECTIONSORT_H