各种排序算法的实现及其比较(三)
w Node();
39 root->key=a[0];
40 for(int i=1; i
10 for(int i=0; i
41 {
42 Insert(root,a[i]);
43 }
44 Printf(root);
45 cout << endl;
46 return 0;
47 }
复制代码
9、基数排序
基数是一种不稳定的排序，它的时间复杂度为O（k*n），k表示最大数的位数，所以当一个序列中有一个很大很大的数时，它排序所花费的时间是非常高昂的。
基数排序的原理是一位一位来排序：先按个位大小排序，再按十位大小排序，接着百位……，一直排到最大位数停止。
比如这样一个数列排序: 342 ，58， 576， 356
第一次排序(个位):
3 4 2
5 7 6
3 5 6
0 5 8
第二次排序(十位):
3 4 2
3 5 6
0 5 8
5 7 6
第三次排序(百位):
0 5 8
3 4 2
3 5 6
5 7 6
结果: 58 342 356 576。
复制代码
1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6
7 int maxdigit(int *a, int n) //返回数组中最大数的位数
8 {
9 int maxx=0;
11 {
12 stringstream sa;
13 sa<
14 string s=sa.str();
15 maxx=max(maxx,int(s.size()));
16 }
17 return maxx;
18 }
19
20 void BaseSort(int *a, int n)
21 {
22 int *count=new int[10];
23 int *tmp=new int[n];
24 int m=maxdigit(a,n);
25 int base=1;
26 for(int i=1; i<=m; i++)
27 {
28 for(int j=0; j<10; j++) count[j]=0;
29 for(int j=0; j
30 {
31 int k=a[j]/base%10;
32 count[k]++;
33 }
34 for(int j=1; j<10; j++)
35 count[j]+=count[j-1];
36 for(int j=n-1; j>=0; j--)
37 {
38 int k=a[j]/base%10;
39 count[k]--;
40 tmp[ count[k] ]=a[j];
41 }