常用排序算法及性能测试
测试算法
- 插入排序
- 冒泡排序
- 快速排序(递归|非递归)
- 归并排序(递归|非递归)
- 堆排序(二叉堆|配对堆(自己玩的,忽略这个))
- 桶排序
- 基数排序
测试代码(合并到同一个文件了)
#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 |