基础算法：Straight Radix Sort的实现分析

作者：[e-mail]
博客：blog.focus-linux.net   linuxfocus.blog.chinaunix.net 

 

本文的copyleft归[e-mail]所有，使用GPL发布，可以自由拷贝，转载。但转载请保持文档的完整性，注明原作者及原链接，严禁用于任何商业用途。

======================================================================================================

前面的文章中学习了Radix排序中的Radix Exchange Sort排序方法，今天学习一下另外一种基于Radix的排序方法——Straight Radix Sort。

需要先交代几句，今天的实现代码完全是来自于《Algorithm In C》中的代码，因为在其示例代码前，我没有真正想明白该算法的思路。结果自己实现的代码写得太差，就不献丑了。当阅读了书中的示例代码后，才明白该算法的思路。没想到几行代码就可以实现了。——因此，标题为实现分析，而非实现呵。

前面的Radix Exchange Sort排序方法的思想是从左向右，即从最高位到最低位，按照基数Radix来检查交换，从而将一个问题划分为两个子问题，从而逐渐完成排序。

今天介绍的Straight Radix Sort算法，则是从右向左检查Radix位。因为右侧为低有效位，所以当在检查该Radix位时，无法保证该位的小值的数字一定比该位的大值的数字要小。因此无法继续使用Radix Exchange Sort的思路。

下面引用书中的一个示意图：

这个就是Straight Radix Sort的排序过程：这里Radix选用的是2，从第一次迭代后，我们无法看出其思路，只能看出迭代后，最低有效位按照0,1进行了排序。重要的是第二次迭代时，同样是按照0,1进行排序，但当该位同时为1时，如何选择哪个数值在前，哪个数值在后。与从右向左来检查Radix位相似，这个选择也是反向的。当检查某一Radix位时，是从最后一个数值开始检查，直到第一个数值。这样做，有一个好处，它保证了该数值为检查过的位数中的数值是最大的——有点拗口。因为该数值越靠后，表明其右侧的数值就越大。这样就保证了，在对该Radix进行排序时，越大的数在不断的向后移动，而越小的数在不断的向前移动。

下面请看实现代码：

#define RADIX_COUNT            (4)
#define RADIX_NUM              (1<<RADIX_COUNT)
void straight_radix_sort(int * orig, int * dest, int size)
{
    int count[RADIX_NUM];
    int i, j;

     /* 

     每次的迭代过程，实际上就是一次Distribution Counting Sort的过程。

     区别无非是有2点：

     1. Distribution时，是根据数组的一部分区间，而非整个儿数值，因此才需要多次迭代；

     2. 再复制到临时数组dest时，是从后向前开始赋值，这样保证大数而逐渐后移。

     */

    for (i = 0; i < 32/RADIX_COUNT; ++i) {
        memset(count, 0, sizeof(count));

        for (j = 0; j < size; ++j) {
            ++count[GET_BITS(orig[j], i*RADIX_COUNT, RADIX_COUNT)];
        }

        for (j = 1; j < RADIX_NUM; ++j) {
            count[j] = count[j-1]+count[j];
        }

         /* 关键点：从后向前赋值，保证大数位于后面 */

        for (j = size-1; j >= 0; --j) {
            dest[--count[GET_BITS(orig[j], i*RADIX_COUNT, RADIX_COUNT)]] = orig[j];
        }

        for (j = 0; j < size; ++j) {
            orig[j] = dest[j];
        }
    }
}

如注释所说，每次迭代即一次Distribution Counting Sort的过程，RADIX_NUM为实际应用的基数Radix——显然，需要其为2的指数。当RADIX_COUNT变为32时，那么就只有一次迭代的过程了，也就蜕变为Distribution Counting Sort。不过临时变量count需要的空间增大到不可接受的地步了。在实际应用中可以选择适当的RADIX_COUNT值。