5. 常用排序算法及性能测试

常用排序算法及性能测试


  • 常用排序算法及性能测试

    测试算法

    1. 插入排序
    2. 冒泡排序
    3. 快速排序（递归|非递归）
    4. 归并排序（递归|非递归）
    5. 堆排序（二叉堆|配对堆（自己玩的，忽略这个））
    6. 桶排序
    7. 基数排序

    测试代码（合并到同一个文件了）

    #include <cstdio>
#include <ctime>
#include <cassert>
#include <algorithm>
#include <random>

using namespace std;

default_random_engine GetRandomInt(time(0));

struct heap {
    int *h;
    int siz;

    int (*cmp)(int, int);

    heap();

    heap(int size, int (*comp)(int, int));

    ~heap();

    void push(int k);

    int pop();
};

struct pheap {
private:
    struct node {
        node *l, *r;
        int k;
    };
    node *root;
    node **arr;

    int (*cmp)(int, int);

#define merge(u, v) (cmp(u->k,v->k)?_merge(v,u):_merge(u,v))

    node *_merge(node *u, node *v);

    node *combine(node *rt);

public:
    pheap();

    pheap(int size, int (*comp)(int, int));

    ~pheap();

    void clear(node *o);

    void push(int k);

    int pop();

};

int cmp_less(int a, int b);

int cmp_greater(int a, int b);

int CheckAnswer(int *arr, int n, int (*cmp)(int, int));

void GetRandomData(int *arr, int n);

void TestInsertSort(int n, int (*cmp)(int, int));

void TestBubbleSort(int n, int (*cmp)(int, int));

int Partition(int *arr, int l, int r, int (*cmp)(int, int));

void MyQuickSort(int *arr, int l, int r, int (*cmp)(int, int));

void TestQuickSort(int n, int (*cmp)(int, int));

void TestQuickSortWithoutRecursion(int n, int (*cmp)(int, int));

void Merge(int *arr, int *tmp, int l, int r, int mid, int (*cmp)(int, int));

void MyMergeSort(int *arr, int *tmp, int l, int r, int (*cmp)(int, int));

void TestMergeSort(int n, int (*cmp)(int, int));

void TestMergeSortWithoutRecursion(int n, int (*cmp)(int, int));

template<typename HeapType>
void TestHeapSort(int n, int (*cmp)(int, int));

void TestBucketSort(int n, int (*cmp)(int, int));

void TestRadixSort(int n, int (*cmp)(int, int));

void test(int f, int t, int n, int (*cmp)(int, int));

void (*SortFunctions[])(int n, int (*cmp)(int, int)) =
        {TestInsertSort,                       //O(n^2)
         TestBubbleSort,                       //O(n^2)
         TestQuickSort,                        //O(nlogn)
         TestQuickSortWithoutRecursion,        //O(nlogn)
         TestMergeSort,                        //O(nlogn)
         TestMergeSortWithoutRecursion,        //O(nlogn)
         TestHeapSort<heap>,                   //O(nlogn)
         TestHeapSort<pheap>,                  //O(nlogn)
         TestBucketSort,                       //O(n)
         TestRadixSort                         //O(n)
        };

char *FunctionNames[] =
        {
                "TestInsertSort",
                "TestBubbleSort",
                "TestQuickSort",
                "TestQuickSortWithoutRecursion",
                "TestMergeSort",
                "TestMergeSortWithoutRecursion",
                "TestHeapSort<heap>",
                "TestHeapSort<pheap>",
                "TestBucketSort",
                "TestRadixSort"
        };

int main() {
    test(0,10,100,cmp_less);
    test(0,10,1000,cmp_greater);
    test(0,10,10000,cmp_less);
    test(0,10,50000,cmp_greater);
    test(2,10,100000,cmp_less);
    test(2,10,1000000,cmp_greater);
    test(2,10,10000000,cmp_greater);
    test(8,10,20000000,cmp_less);
    test(8,10,50000000,cmp_greater);
    test(8,10,100000000,cmp_less);
    return 0;
}

void GetRandomData(int *arr, int n) {
    for (int i = 0; i < n; ++i)arr[i] = GetRandomInt();
}

void TestInsertSort(int n, int (*cmp)(int, int)) {
    int *arr = (int *) malloc(n * sizeof(int));
    assert(arr);
    GetRandomData(arr, n);
    int *SwapPtr;
    for (int i = 0; i < n; ++i) {
        SwapPtr = arr + i;
        for (int j = i; j < n; ++j)
            if (cmp(*SwapPtr, arr[j]))
                SwapPtr = arr + j;
        swap(*SwapPtr, arr[i]);
    }
    assert(CheckAnswer(arr, n, cmp));
    free(arr);
}

void TestBubbleSort(int n, int (*cmp)(int, int)) {
    int *arr = (int *) malloc(n * sizeof(int));
    assert(arr);
    GetRandomData(arr, n);
    for (int i = 0, flag = 1; i < n && flag; ++i) {
        flag = 0;
        for (int j = n - 1; j > i; --j)
            if (cmp(arr[j - 1], arr[j])) {
                swap(arr[j - 1], arr[j]);
                flag = 1;
            }
    }
    assert(CheckAnswer(arr, n, cmp));
    free(arr);
}

int Partition(int *arr, int l, int r, int (*cmp)(int, int)) {
    int i = rand() % (r - l + 1) + l, temp = arr[i];
    arr[i] = arr[l];
    arr[l] = temp;
    i = l;
    for (int j = l + 1; j <= r; ++j)
        if (cmp(temp, arr[j]))
            swap(arr[++i], arr[j]);
    swap(arr[l], arr[i]);
    return i;
}

void MyQuickSort(int *arr, int l, int r, int (*cmp)(int, int)) {
    if (l >= r)return;
    int i = Partition(arr, l, r, cmp);
    MyQuickSort(arr, l, i - 1, cmp);
    MyQuickSort(arr, i + 1, r, cmp);
}

void TestQuickSort(int n, int (*cmp)(int, int)) {
    int *arr = (int *) malloc(n * sizeof(int));
    assert(arr);
    GetRandomData(arr, n);
    MyQuickSort(arr, 0, n - 1, cmp);
    assert(CheckAnswer(arr, n, cmp));
    free(arr);
}

void TestQuickSortWithoutRecursion(int n, int (*cmp)(int, int)) {
    int *arr = (int *) malloc(n * sizeof(int));
    assert(arr);
    int *stack = (int *) malloc(n * sizeof(int));
    assert(stack);
    GetRandomData(arr, n);
    stack[0] = 0;
    stack[1] = n - 1;
    for (int top = 2; top;) {
        int r = stack[--top], l = stack[--top];
        if (l < r) {
            int i = Partition(arr, l, r, cmp);
            stack[top++] = l;
            stack[top++] = i;
            stack[top++] = i + 1;
            stack[top++] = r;
        }
    }
    assert(CheckAnswer(arr, n, cmp));
    free(arr);
    free(stack);
}

void Merge(int *arr, int *tmp, int l, int r, int mid, int (*cmp)(int, int)) {
    int i = l, j = mid + 1, k = l - 1;
    while (i <= mid && j <= r)
        tmp[++k] = arr[cmp(arr[j], arr[i]) ? i++ : j++];
    while (i <= mid)tmp[++k] = arr[i++];
    while (j <= r)tmp[++k] = arr[j++];
    for (i = l; i <= r; ++i)arr[i] = tmp[i];
}

void MyMergeSort(int *arr, int *tmp, int l, int r, int (*cmp)(int, int)) {
    if (l >= r)return;
    int mid = l + r >> 1;
    MyMergeSort(arr, tmp, l, mid, cmp);
    MyMergeSort(arr, tmp, mid + 1, r, cmp);
    Merge(arr, tmp, l, r, mid, cmp);
}

void TestMergeSort(int n, int (*cmp)(int, int)) {
    int *arr = (int *) malloc(n * sizeof(int));
    assert(arr);
    int *tmp = (int *) malloc(n * sizeof(int));
    assert(tmp);
    GetRandomData(arr, n);
    MyMergeSort(arr, tmp, 0, n - 1, cmp);
    assert(CheckAnswer(arr, n, cmp));
    free(arr);
    free(tmp);
}

void TestMergeSortWithoutRecursion(int n, int (*cmp)(int, int)) {
    int *arr = (int *) malloc(n * sizeof(int));
    assert(arr);
    int *tmp = (int *) malloc(n * sizeof(int));
    assert(tmp);
    GetRandomData(arr, n);
    int step = 2, i;
    for (; step <= n; step <<= 1) {
        for (i = 0; i + step <= n; i += step)
            Merge(arr, tmp, i, i + step - 1, i + i + step - 1 >> 1, cmp);
        Merge(arr, tmp, i - step, n - 1, i - 1, cmp);
    }
    Merge(arr, tmp, 0, n - 1, (step >> 1) - 1, cmp);
    assert(CheckAnswer(arr, n, cmp));
    free(arr);
    free(tmp);
}

template<typename HeapType>
void TestHeapSort(int n, int (*cmp)(int, int)) {
    int *arr = (int *) malloc(n * sizeof(int));
    assert(arr);
    HeapType heap(n, cmp);
    int top = 1;
    GetRandomData(arr, n);
    for (int i = 0; i < n; ++i)heap.push(arr[i]);
    for (int i = 0; i < n; ++i)arr[i] = heap.pop();
    assert(CheckAnswer(arr, n, cmp));
    free(arr);
}

void TestBucketSort(int n, int (*cmp)(int, int)) {
    int *arr = (int *) malloc(n * sizeof(int));
    assert(arr);
    const int bucketsize = 10000000;
    int *bucket = (int *) malloc(bucketsize * sizeof(int));
    assert(bucket);
    GetRandomData(arr, n);
    for (int i = 0; i < n; ++i)arr[i] %= bucketsize;
    for (int i = 0; i < n; ++i)++bucket[arr[i]];
    if (cmp(1, 0))
        for (int i = 0, *ptr = arr; i < bucketsize; ++i)
            while (bucket[i]--)*ptr++ = i;
    else
        for (int i = bucketsize - 1, *ptr = arr; i >= 0; --i)
            while (bucket[i]--)*ptr++ = i;
    assert(CheckAnswer(arr, n, cmp));
    free(arr);
    free(bucket);
}

void TestRadixSort(int n, int (*cmp)(int, int)) {
    int *arr = (int *) malloc(n * sizeof(int));
    assert(arr);
    int *tmp = (int *) malloc((n + 1) * sizeof(int));
    assert(tmp);
    int *cnt = (int *) malloc(65536 * sizeof(int));
    assert(cnt);
    GetRandomData(arr, n);
    for (int i = 0; i <= 65535; ++i)cnt[i] = 0;
    for (int i = 0; i < n; ++i)++cnt[arr[i] & 65535];
    if (cmp(1, 0))for (int i = 1; i <= 65535; ++i)cnt[i] += cnt[i - 1];
    else for (int i = 65534; i >= 0; --i)cnt[i] += cnt[i + 1];
    for (int i = n - 1; i >= 0; --i)tmp[--cnt[arr[i] & 65535]] = arr[i];
    for (int i = 0; i <= 65535; ++i)cnt[i] = 0;
    for (int i = 0; i < n; ++i)++cnt[tmp[i] >> 16];
    if (cmp(1, 0))for (int i = 1; i <= 65535; ++i)cnt[i] += cnt[i - 1];
    else for (int i = 65534; i >= 0; --i)cnt[i] += cnt[i + 1];
    for (int i = n - 1; i >= 0; --i)arr[--cnt[tmp[i] >> 16]] = tmp[i];
    assert(CheckAnswer(arr, n, cmp));
    free(arr);
    free(tmp);
    free(cnt);
}

void test(int f, int t, int n, int (*cmp)(int, int)) {
    printf("### Data scale:%d\n|Sort Algorithm|Running time(s)|\n|-|-|\n", n);
    double runtime;
    for (int i = f; i < t; ++i) {
        runtime = clock();
        SortFunctions[i](n,cmp);
        //printf("%-32s:%8.3lf s\n",FunctionNames[i] ,(clock() - runtime) / CLOCKS_PER_SEC);
        printf("|%s|%.3lf|\n",FunctionNames[i] ,(clock() - runtime) / CLOCKS_PER_SEC);
    }
    puts("");
}

int cmp_greater(int a, int b) {
    return a > b;
}

int cmp_less(int a, int b) {
    return a < b;
}

int CheckAnswer(int *arr, int n, int (*cmp)(int, int)) {
    for (int i = 1; i < n; ++i)
        if (cmp(arr[i - 1], arr[i]))return 0;
    return 1;
}


heap::heap() {
    h = (int *) malloc(1000 * sizeof(int));
    assert(h);
    siz = 0;
    cmp = cmp_less;
}

heap::heap(int size, int (*comp)(int, int)) {
    h = (int *) malloc(size * sizeof(int));
    assert(h);
    siz = 0;
    cmp = comp;
}

heap::~heap() {
    assert(h);
    free(h);
}

void heap::push(int k) {
    int now = ++siz, fa;
    for (h[now] = k; fa = now >> 1; now = fa)
        if (cmp(h[fa], k))
            h[now] = h[fa];
        else break;
    h[now] = k;
}

int heap::pop() {
    int ret = h[1];
    int now = 1, c, d;
    for (d = h[siz]; (c = now << 1) <= siz - 1; now = c) {
        if (cmp(h[c], h[c | 1]))c |= 1;
        if (cmp(d, h[c]))h[now] = h[c];
        else break;
    }
    h[now] = d;
    return ret;
}

pheap::pheap() {
    root = 0;
    arr = (node **) malloc(1000 * sizeof(node *));
    assert(arr);
    cmp = cmp_less;
}

pheap::pheap(int size, int (*comp)(int, int)) {
    root = 0;
    arr = (node **) malloc(size * sizeof(node *));
    assert(arr);
    cmp = comp;
}

pheap::~pheap() {
    free(arr);
    clear(root);
}

void pheap::clear(node *o) {
    if (o == 0)return;
    if (o->l)clear(o->l);
    if (o->r)clear(o->r);
    free(o);
}

pheap::node *pheap::_merge(pheap::node *u, pheap::node *v) {
    v->r = u->l;
    u->l = v;
    return u;
}

pheap::node *pheap::combine(pheap::node *rt) {
    if (rt->r == 0)return rt;
    int j = -1;
    for (; rt != 0; rt = rt->r)arr[++j] = rt;
    for (int i = 0; i < j; i += 2)arr[i] = merge(arr[i], arr[i | 1]);
    for (j & 1 != 0 ? j ^= 1 : 0; j > 0; j -= 2)arr[j - 2] = merge(arr[j - 2], arr[j]);
    return arr[0];
}

void pheap::push(int k) {
    node *t = (node *) malloc(sizeof(node));
    assert(t);
    t->k = k;
    t->l = t->r = 0;
    root = root != 0 ? merge(root, t) : t;
}

int pheap::pop() {
    assert(root);
    int ret = root->k;
    root = root->l != 0 ? combine(root->l) : 0;
    return ret;
}

    测试结果

    Data scale:100

    Sort Algorithm Running time(s)
    TestInsertSort 0.000
    TestBubbleSort 0.000
    TestQuickSort 0.000
    TestQuickSortWithoutRecursion 0.000
    TestMergeSort 0.000
    TestMergeSortWithoutRecursion 0.000
    TestHeapSort<heap> 0.000
    TestHeapSort<pheap> 0.000
    TestBucketSort 0.085
    TestRadixSort 0.002

    Data scale:1000

    Sort Algorithm Running time(s)
    TestInsertSort 0.004
    TestBubbleSort 0.010
    TestQuickSort 0.000
    TestQuickSortWithoutRecursion 0.001
    TestMergeSort 0.000
    TestMergeSortWithoutRecursion 0.000
    TestHeapSort<heap> 0.001
    TestHeapSort<pheap> 0.001
    TestBucketSort 0.079
    TestRadixSort 0.002

    Data scale:10000

    Sort Algorithm Running time(s)
    TestInsertSort 0.335
    TestBubbleSort 1.063
    TestQuickSort 0.005
    TestQuickSortWithoutRecursion 0.006
    TestMergeSort 0.004
    TestMergeSortWithoutRecursion 0.004
    TestHeapSort<heap> 0.005
    TestHeapSort<pheap> 0.011
    TestBucketSort 0.080
    TestRadixSort 0.002

    Data scale:50000

    Sort Algorithm Running time(s)
    TestInsertSort 8.253
    TestBubbleSort 27.319
    TestQuickSort 0.027
    TestQuickSortWithoutRecursion 0.032
    TestMergeSort 0.023
    TestMergeSortWithoutRecursion 0.022
    TestHeapSort<heap> 0.026
    TestHeapSort<pheap> 0.061
    TestBucketSort 0.083
    TestRadixSort 0.005

    Data scale:100000

    Sort Algorithm Running time(s)
    TestQuickSort 0.053
    TestQuickSortWithoutRecursion 0.068
    TestMergeSort 0.048
    TestMergeSortWithoutRecursion 0.049
    TestHeapSort<heap> 0.044
    TestHeapSort<pheap> 0.137
    TestBucketSort 0.088
    TestRadixSort 0.009

    Data scale:1000000

    Sort Algorithm Running time(s)
    TestQuickSort 0.656
    TestQuickSortWithoutRecursion 0.776
    TestMergeSort 0.568
    TestMergeSortWithoutRecursion 0.562
    TestHeapSort<heap> 0.773
    TestHeapSort<pheap> 2.170
    TestBucketSort 0.166
    TestRadixSort 0.075

    Data scale:10000000

    Sort Algorithm Running time(s)
    TestQuickSort 7.629
    TestQuickSortWithoutRecursion 9.042
    TestMergeSort 6.492
    TestMergeSortWithoutRecursion 6.636
    TestHeapSort<heap> 10.480
    TestHeapSort<pheap> 33.426
    TestBucketSort 0.909
    TestRadixSort 0.904

    Data scale:20000000

    Sort Algorithm Running time(s)
    TestBucketSort 1.608
    TestRadixSort 1.876

    Data scale:50000000

    Sort Algorithm Running time(s)
    TestBucketSort 3.556
    TestRadixSort 4.985

    Data scale:100000000

    Sort Algorithm Running time(s)
    TestBucketSort 6.776
    TestRadixSort 10.286
    回复 引用 0
回复
 

Copyright © 2018 bbs.dian.org.cn All rights reserved.

与 Dian 的连接断开，我们正在尝试重连，请耐心等待