2011-08-01 17:26:20Morris
[分析] ZJ 排序大車拼
由於 2011/8/1 看到討論區, 砲轟連連, 有感而發
ZJ 上面充斥著排序題, 我就懶得再多做說明了,
看到排序題, 我自己都煩了, 不過效率大家總是認為O(nlogn)最快, 現在來做一下分析,
先限定數字個數小於 1000萬, 每個數字介於 0 ~ 2147483647
1. Std::sort 內建排序, 這應該不用多做說明
2. Radix sort 基數排序 O(8n)
3. Merge sort 合併排序 O(nlogn)
4. Sleep sort ...
5. Splay tree 伸展樹
6. AVL tree 平衡樹
7. Heap sort 堆積排序
(下面的速度全部沒有包括輸出, 但是 heap sort 輸出也要 nlogn, 因此下面的消耗時間要 *2)
8. bin+insert 分堆的插入排序,
下面程式碼是將 2147483647 分成 10萬堆, 也就是 [0,21474]做一組
(1) n = 10,0000
排序類別 消耗時間
Radix sort 0.026000s
Merge sort 0.041000s
Sleep sort 100000s
Splay tree 0.095000s
AVL tree 0.111000s
Heap sort 0.026000s
bin+insert 0.001000s
(2) n = 100,0000
排序類別 消耗時間
Std::sort 0.378000s
Radix sort 0.258000s
Merge sort 0.434000s
Sleep sort 1000000s
Splay tree 1.449000s
AVL tree 1.826000s
Heap sort 0.256000s
bin+insert 0.445000s
(3) n = 250,0000
排序類別 消耗時間
Radix sort 0.625000s
Merge sort 1.140000s
Sleep sort 2500000s
Splay tree 4.178000s
AVL tree 5.371000s
Heap sort 0.647000s
bin+insert 1.865000s
(4) n = 500,0000
排序類別 消耗時間
Radix sort 1.291000s
Merge sort 2.270000s
Sleep sort 5000000s
Splay tree 9.392000s
AVL tree 11.813000s
Heap sort 1.291000s
bin+insert 6.179000s
(5) n = 1000,0000
排序類別 消耗時間
Radix sort 2.591000s
Merge sort 4.655000s
Sleep sort 10000000s
Splay tree 21.581000s
AVL tree 26.241000s
Heap sort 2.597000s
bin+insert 23.127000s
測試程式碼 :
1. Std::sort
#include<iostream>
int T,n,t[10000000],i,l,top=0,r;
bool q=0;
main()
{
freopen("in1.txt", "rt", stdin);
freopen("out2.txt", "w+t", stdout);
clock_t st, ed;
st = clock();
while(scanf("%d", &t[top]) == 1) top++;
/*for(i=0;i<l;i++)
{
if(a[i]>='0'&&a[i]<='9')
r=r*10+a[i]-'0',q=1;
else if(q)t[top++]=r,r=0,q=0;
}
if(q)t[top++]=r;*/
std::sort(t,t+top);
/*for(i=0;i<top;i++)printf("%d ",t[i]);*/
ed = clock();
printf("%f\n", (float)(ed - st )/CLOCKS_PER_SEC);
}
2.Radix sort
#include<stdio.h>
#include<time.h>
#define MaxN 10000001
void RadixSort(int *A, int *B, int n) {
int a, x, d, *T, C[256];
for(x = 0; x < 4; x++) {
d = x*8;
for(a = 0; a < 256; a++) C[a] = 0;
for(a = 0; a < n; a++) C[(A[a]>>d)&255]++;
for(a = 1; a < 256; a++) C[a] += C[a-1];
for(a = n-1; a >= 0; a--) B[--C[(A[a]>>d)&255]] = A[a];
T = A, A = B, B = T;
}
}
int S0[MaxN], S1[MaxN];
main() {
freopen("in1.txt", "rt", stdin);
freopen("out1.txt", "w+t", stdout);
int n = 0, a;
clock_t st, ed;
st = clock();
while(scanf("%d", &S0[n]) == 1) n++;
RadixSort(S0, S1, n);
/*for(a = 0; a < n; a++)
printf("%d ", S0[a]);
puts("");*/
ed = clock();
printf("%f\n", (float)(ed - st )/CLOCKS_PER_SEC);
return 0;
}
3.Merge sort
#include <stdio.h>
#include<time.h>
void MergeSort(int, int);
void Merge(int, int, int);
int Data[10000001], X[10000001];
int main() {
freopen("in1.txt", "rt", stdin);
freopen("out3.txt", "w+t", stdout);
clock_t st, ed;
st = clock();
int n = 0;
while(scanf("%d", &Data[n]) == 1) n++;
MergeSort(0, n-1);
/*
for(i = 0; i < n; i++)
printf("%d ", numbers[i]);*/
ed = clock();
printf("%f\n", (float)(ed - st )/CLOCKS_PER_SEC);
return 0;
}
void MergeSort(int l, int h) {
if(l < h) {
int m = (l+h)/2;
MergeSort(l, m);
MergeSort(m+1, h);
Merge(l, m, h);
}
}
void Merge(int l, int m, int h) {
int In1 = l, In2 = m+1;
int a, b, Top = 0;
while(In1 <= m && In2 <= h) {
if(Data[In1] < Data[In2])
X[Top++] = Data[In1++];
else
X[Top++] = Data[In2++];
}
while(In1 <= m) X[Top++] = Data[In1++];
while(In2 <= h) X[Top++] = Data[In2++];
for(a = 0, b = l; a < Top; a++, b++)
Data[b] = X[a];
}
感謝 example & leopan0922
很有用的結果，推一個。不過輸入應該要排除在計時之外吧，還有heap sort 輸出要O(nlogn)這句話，我不太懂耶?