链表应用：基数排序

在基数排序（ radix sort）中，把数按照某种基数分解为数字，然后对数字进行排序。
例3-1 假定对范围在 0 ~ 9 9 9之间的 1 0个整数进行排序。如果使用 r a n g e = 1 0 0 0来调用 B i n S o r t，那么箱子的初始化将需要 1 0 0 0个执行步，节点分配需要 1 0个执行步，从箱子中收集节点需要 1 0 0 0个执行步，总的执行步数为 2 0 1 0。另一种方法是：
1) 用 B i n S o r t根据数的最低位数字对 1 0个数进行排序。由于每个数字的范围为 0 ~ 9，因此r a n g e = 1 0。图3-17a 给出了具有 1 0个数的链表，图 3-17b 给出了按最低位数字排序后的链表。
2) 用箱子排序算法对1) 中所得到的链表按次低位数字进行排序。同样，有 r a n g e = 1 0。由于箱子排序是稳定排序，次低位数字相同的节点，其相对次序保持不变（与按最低位数字排序时所得到的次序相同）。因此，现在链表是按照最后两位数字进行排序的。图 3-17c 给出了相应的排序结果。
3) 用箱子排序算法对 2) 中所得到的链表按第三位 (最高位 )数字进行排序。 (如果一个数仅包含两位数字，则其第三位数字为 0 )。由于按第三位数字排序是稳定排序，所以第三位数字相同的节点，其相对次序保持不变（与按最后两位数字排序时所得到的次序相同）。因此，现在链表是按照后三位数字进行排序的。图 3-17d 给出了相应的排序结果。

简单的说，基数排序是用一个基r将链表中的数进行分解，然后对分解后的数进行箱子排序。

当使用基数 r=n对n个介于 0 ~n ^c- 1 范围内的整数进行分解时，每个数将可以分解出 c个数字。因此，可以采用 c 次箱子排序，每次排序时取 r a n g e =n。整个排序所需要的时间为O (c n) = O(n)（因为c 是一个常量）。

实现：

参数range为数的范围，radix为基

 1 template<class T>
 2 void Chain<T>::Radixsort(int range,int radix)
 3 {
 4     int cnt = 0;
 5     int r = range-1;
 6     while (r)
 7     {
 8         cnt++;
 9         r /= radix;
10     }
11     int radix1 = radix;
12     int radix2=1;
13     ChainNode<T> **bottom, **top;
14     //箱子初始化
15     bottom = new ChainNode<T>*[radix];
16     top = new ChainNode<T>*[radix];
17     for (int i = 1; i <= cnt;++i)
18     {
19         int b;//箱子索引号
20         
21         
22         for (b = 0; b < radix; b++)
23         {
24             bottom[b] = 0;
25         }
26 
27         for (; first; first = first->link)
28         {
29             b = first->data%(radix1)/radix2;
30             if (bottom[b])
31             {
32                 top[b]->link = first;
33                 top[b] = first;
34             }
35             else
36             {
37                 bottom[b] = top[b] = first;
38             }
39         }
40 
41         ChainNode<T> *y = 0;
42         for (b = 0; b < radix; b++)
43         {
44             if (bottom[b])
45             {
46                 if (y)
47                     y->link = bottom[b];
48                 else
49                     first = bottom[b];
50 
51                 y = top[b];
52             }
53         }
54         if (y) y->link = 0;
55         
56 
57         radix2 *= radix;
58         radix1 *= radix;
59         
60     }
61     delete[] bottom;
62     delete[] top;
63 }

View Code

Binsort（链表应用：箱子排序）与Radixsort的比较：

 1 #include "Chain.h"
 2 
 3 #include <cstdlib>
 4 #include <time.h>
 5 #include <sys/timeb.h>
 6 int main()
 7 {
 8     Chain<int> C;
 9     srand(time(NULL));
10     time_t starttime, endtime;
11     timeb time1, time2;
12     int n = 1e6;
13     //产生1000个0~1e6范围内的数，存入链表
14     for (int i = 0; i < 1000;++i)
15     {
16         int x = rand() % n;
17         C.Insert(0, x);
18     }
19 
20     cout << "start BinSort" << endl;
21     
22     ftime(&time1);
23     time(&starttime);
24 
25     C.Binsort(n);
26     ftime(&time2);
27     time(&endtime);
28     cout << difftime(endtime, starttime)+time2.millitm-time1.millitm << endl;
29     
30     ftime(&time1);
31     time(&starttime);
32 
33     C.Radixsort(n, 100);
34 
35     ftime(&time2);
36     time(&endtime);
37     cout << difftime(endtime, starttime) + time2.millitm - time1.millitm << endl;
38 
39 
40     system("pause");
41 
42     return 0;
43 }

View Code