首页 > 代码库 > 常见排序算法导读(10)[基数排序]

常见排序算法导读(10)[基数排序]

2024-09-11 16:26:34   207人阅读

与前面介绍的7种排序算法不同，基数排序(Radix Sort)是基于多关键字排序的一种排序算法。也就是说，前面介绍的7种排序算法是建立在对单个元素关键字比较的基础之上，而基数排序则是采用"分配"与"收集"的办法，用对多关键字进行排序的思想实现对单个关键字的排序。

基数排序的典型例子当然就是扑克牌排序啦,几乎所有的数据结构教科书都会讲到，原因是形象易懂。每张扑克牌都有两个关键字：花色和面值。假定有序关系为：

  • 花色： 黑桃 < 红桃 < 梅花 < 方块
  • 面值： 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A

如果把所有扑克牌排成下列次序：

  • 黑桃2, ..., 黑桃A, 红桃2, ..., 红桃A, 梅花2, ..., 梅花A, 方块2, ..., 方块A。

那么这就是多关键字排序。排序后形成的有序序列叫做词典有序序列。 对于扑克牌排序，有两种方法。可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序。

再举个对数字进行基数排序的例子，

技术分享

基数排序的基本思想

设待排记录中的多个关键字为K1, K2, ..., Kr。K1第1关键字，Kr为第r关键字。由记录R1, R2, ..., Rn组成的表关于关键字K1, K2, ..., Kr有序，当且仅当对每一对记录Ri < Rj 都有(K1i, K2i, ..., Kri) <= (K1j, K2j, ..., Krj)。

基数排序的分类

  1. 最高位优先MSD(Most Significant Digit first)
  2. 最低位优先LSD(Least Significant Digit fisrt)

技术分享

基于LSD实现的基数排序相对简单。(P.S. 在观看了Radix Sort Visualization之后，我大约花了15分钟就完成了代码实现，比啃数据结构的书容易多了。)

  1 /*
  2  * Get the digit of number by index(= 0, 1, 2, ...)
  3  *
  4  * e.g.
  5  *     num = 6543210
  6  *     ------+------
  7  *     index | digit
  8  *     ------+------
  9  *         0 | 0
 10  *         1 | 1
 11  *         2 | 2
 12  *         3 | 3
 13  *         4 | 4
 14  *         5 | 5
 15  *         6 | 6
 16  *         7 | 0
 17  *        .. | ..
 18  *     ------+------
 19  */
 20 unsigned char
 21 get_digit_byindex(int num, unsigned int index)
 22 {
 23         int q = 0; /* quotient */
 24         int r = 0; /* remainder */
 25         for (int i = index; i >= 0; i--) {
 26                 r = num % 10;
 27                 q = num / 10;
 28                 num = q;
 29         }
 30 
 31         return (unsigned char)r;
 32 }
 33 
 34 /*
 35  * Get width of a number
 36  * e.g.
 37  *     0 .. 9   ; width = 1
 38  *    10 .. 99  ; width = 2
 39  *   100 .. 999 ; width = 3
 40  *   ... .. ...
 41  */
 42 static int
 43 get_width_of_num(int num)
 44 {
 45         if (num < 0)
 46                 num = 0 - num;
 47 
 48         int w = 1;
 49         for (int q = num / 10; q != 0; q /= 10)
 50                 w++;
 51         return w;
 52 }
 53 
 54 /*
 55  * Build bin[] by index(=0, 1, ..., N-1) (N is the max width of num in a[])
 56  *
 57  * NOTE: This is the core to understand radix sorting based on LSD
 58  */
 59 static void
 60 build_bin_byindex(int bin[], size_t nb, int a[], size_t na, int index)
 61 {
 62         /* 1. always reset bin[] */
 63         for (int i = 0; i < nb; i++)
 64                 bin[i] = 0;
 65 
 66         /* 2. init bin[] by walking a[] */
 67         for (int i = 0; i < na; i++) {
 68                 unsigned char d = get_digit_byindex(a[i], index);
 69                 bin[d] += 1;
 70         }
 71 
 72         /* 3. build bin[] */
 73         for (int i = 1; i < nb; i++)
 74                 bin[i] += bin[i-1];
 75 }
 76 
 77 void
 78 radixsort(int a[], int n)
 79 {
 80         /* get the max width of num in a[] */
 81         int maxwidth = 0;
 82         for (int i = 0; i < n; i++) {
 83                 int width = get_width_of_num(a[i]);
 84                 if (width > maxwidth)
 85                         maxwidth = width;
 86         }
 87 
 88         /* alloc bin[] to store the number of per digit */
 89         int bin[10] = { 0 };
 90 
 91         /* alloc aux[] to save a[] while rebuilding a[] */
 92         int *aux = (int *)malloc(sizeof(int) * n);
 93 
 94         /* LSD (Least Significant Digit first) */
 95         for (int index = 0; index < maxwidth; index++) {
 96                 /* 1. build bin[] */
 97                 build_bin_byindex(bin, 10, a, n, index);
 98 
 99                 /* 2. copy a[] to aux[] */
100                 for (int i = 0; i < n; i++)
101                         aux[i] = a[i];
102 
103                 /* 3. reset a[] */
104                 for (int i = 0; i < n; i++)
105                         a[i] = 0;
106 
107                 /* 4. rebuild a[] */
108                 for (int i = n - 1; i >= 0; i--) {
109                         unsigned char d = get_digit_byindex(aux[i], index);
110                         int j = bin[d] - 1;
111                         a[j] = aux[i];
112                         bin[d]--;
113                 }
114         }
115 
116         free(aux);
117 }

 

参考资料：

  1. Radix Sort Visualization
  2. Radix sort

常见排序算法导读(10)[基数排序]


联系
我们