数据结构之几种排序方式速度的比较

测试程序如下：

#include<iostream>
#include<chrono>
#include<string>
#include<random>
#include<algorithm>
using namespace std;
namespace kedixa
{

    class timer
    {
        typedef std::chrono::steady_clock::time_point   tp;
        typedef std::chrono::duration<double>           dd;
        typedef std::chrono::steady_clock               sc;
    private:
        tp _begin;
        dd _span;
    public:
        timer()
            : _begin(tp()), _span(dd(0)) {}
        void start()
        {
            _begin = sc::now();
        }

        void pause()
        {
            tp _end = sc::now();
            _span += std::chrono::duration_cast<dd>(_end - _begin);
        }

        void stop(std::string head = std::string(),
            std::string tail = std::string())
        {
            tp _end = sc::now();
            _span += std::chrono::duration_cast<dd>(_end - _begin);
            std::cout << head << _span.count() << " seconds" << tail << std::endl;
            _span = dd(0);
        }
        ~timer()
        {}
    };

} // namespace

#define maxSize 110000

void create(long long int arr[])
{
    std::default_random_engine random;

    for (int i = 1; i < maxSize; ++i)
        arr[i] = random() % maxSize;

}
void bubbleSort(long long int arr[])
{
    bool flag;
    long long int temp;
    int i = 1;
    do {
        flag = false;
        for (int j = maxSize-1; j >= i; --j)
            if (arr[j] < arr[j - 1]) {
                temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                flag = true;
            }
        ++i;
    } while (flag == true && i <= maxSize-1);
}
void insertSort(long long int arr[])
{   
    long long int temp; int j;
    for (int i = 1; i < maxSize; ++i) {
        temp = arr[i];
        j = i - 1;
        while (arr[j] > temp && j>=0) {
            arr[j + 1] = arr[j]; --j;
        }
        arr[j + 1] = temp;
    }
}
void shellSort(long long int arr[])
{
    int dl = maxSize / 2; int j;
    long long int temp;
    while (dl >= 1) {
        for (int i = dl; i < maxSize; ++i) {
            temp = arr[i];
            j = i - dl;
            while (arr[j] > temp &&j > dl-2) {
                arr[j + dl] = arr[j];
                j = j - dl;
            }
            arr[j + dl] = temp;
        }
        dl = dl / 2;
    }
}
void partition(long long int arr[maxSize], int s, int t, int &cut) {
    long long int x = arr[s];
    int i = s,j = t;
    while (i != j) {
        while (i < j && arr[j] > x)--j;
        if (i < j) { arr[i] = arr[j]; ++i; }
        while (i < j && arr[i] < x)i++;
        if (i < j) { arr[j] = arr[i]; --j; }
        arr[i] = x;
        cut = i;
    }
}
void quickSort(long long int arr[maxSize], int s, int t) {
    int i;
    if (s < t) {
        partition(arr, s, t, i);
        quickSort(arr, s, i - 1);
        quickSort(arr, i + 1, t);
    }
}
void selectSort(long long int arr[maxSize]) {
    long long int temp;
    for (int i = 0; i < maxSize - 1; ++i) {
        int min = i;
        for (int j = i + 1; j < maxSize; j++)
            if (arr[j] < arr[min])min = j;
        if (min != i) {
            temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }
}
void sift(long long int arr[maxSize], int k, int m) {
    bool finish = false;
    long long int x = arr[k];
    int i = k;
    int j = 2 * i;
    while (j <= m && !finish) {
        if (j < m&&arr[j] < arr[j + 1])++j;
        if (x >= arr[j]) finish = true;
        else {
            arr[i] = arr[j];
            i = j; j = 2 * j;
        }
    }
    arr[i] = x;
}
void heapSort(long long int arr[maxSize],int n) {
    long long int temp;
    for (int i = n / 2; i >= 1; --i)
        sift(arr, i, n);
    for (int i = n; i >= 2; i--) {
        temp = arr[i];
        arr[i] = arr[1];
        arr[1] = temp;
        sift(arr, 1, i - 1);
    }
}
int main()
{
    using kedixa::timer; // 使用命名空间
    timer t; // 定义一个计时器
    long long int arr[maxSize];

    create(arr);
    t.start();
    sort(arr+1,arr+maxSize);
    t.stop(string("sort in algorithm takes "), string("."));

    create(arr);
    t.start();
    heapSort(arr,maxSize-1);
    t.stop(string("heapSort takes "), string("."));

    create(arr);
    t.start();
    selectSort(arr);
    t.stop(string("selectSort takes "), string("."));

    create(arr);
    t.start();
    quickSort(arr, 1, maxSize - 1);
    t.stop(string("quickSort takes "), string("."));

    create(arr);
    t.start();
    insertSort(arr);
    t.stop(string("insertSort takes "), string("."));

    create(arr);
    t.start();
    shellSort(arr);
    t.stop(string("shellSort takes "), string("."));

    create(arr);
    t.start();
    bubbleSort(arr);
    t.stop(string("bubbleSort takes "), string("."));

    int f;
    cin >> f;
    return 0;
}

总共测试了7种排序方式，分别为：

• 插入排序以及其改进的希尔排序
• 快排
• 选择排序
• 堆排序
• 冒泡排序
• algorithm库中的sort排序

测试结果如下：
sort in algorithm takes 0.251248 seconds.
heapSort takes 0.0350618 seconds.
selectSort takes 24.2002 seconds.
quickSort takes 0.0221955 seconds.
insertSort takes 10.9588 seconds.
shellSort takes 0.0466631 seconds.
bubbleSort takes 52.15 seconds.

可以看到，不同的排序性能差异非常大。
最快的快排，最慢的冒泡排序。
其中冒泡排序所花时间大约是快排的2 349倍。
另外，我原本以为algorithm库中的sort函数应该挺快的，结果还是比自己写的快排慢了很多。这个应该是测试数据的问题。
在maxSize大于100k时，会发生栈溢出，应该是快速排序递归调用的过程中发生了栈溢出。