基础算法：Radix Exchange Sort的实现

951阅读　0评论2012-02-16　十七岁的回忆
分类：

作者：gfree.wind@gmail.com
博客：blog.focus-linux.net   linuxfocus.blog.chinaunix.net 
 
本文的copyleft归gfree.wind@gmail.com所有，使用GPL发布，可以自由拷贝，转载。但转载请保持文档的完整性，注明原作者及原链接，严禁用于任何商业用途。
======================================================================================================
为了弥补自己算法的短板，继续基础算法的学习。今天要学习的是Radix排序的一种实现——Radix Exchange Sort。

Radix排序，顾名思义就是根据Radix即基数来排序。比如四个数100，12， 103，9按照10为基数的话，先从最高位开始，即百位开始，百位为0的数值一定在百位为1的数值前面。这时数值就分为了2组，然后再分别检查十位，十位为0的数值一定在十位为1的数值前面，直到检查到个位。这时，整个儿的排序已经完成。

如果是我们自己来排序，以10为基数很自然——谁让我们是10个手指头呢。但是计算机是二进制的，所以对于让计算机执行的Radix Sort来说，选择基数为2更为自然。但基本思想是一样的。

个人认为，Radix Sort并不适合直接对数值进行排序，因为按基数取值的运算对于数值的比较来说，并不值得的。我认为Radix Sort比较适合应用于多key按照优先级比较的场合。今天为了简单，仍然使用数值来演示。

Radix Exchange Sort的主要思想，按照基数，从最高位开始检查，直至最低位。将该位为0的数置于该位为1的数值前面。然后将该位同0的数值和同1的数值分别检查下一位，直至检查到最低位，这时就完成了排序。根据这个思想，很自然就可以想到需要用递归来实现。

按照这个思路，我写了下面这个实现：
  1. //得到从k位开始的n个bits
  2. #define GET_BITS(bytes, k, n) \
  3.     ((bytes>>k) & ~((~0)<<n))


  6. void radix_exchange_sort(int *array, int size)
  7. {
  8.     real_radix_exchange_sort(array, 0, size-1, 31);
  9. }

 /* left为第一个索引，right为最后一个索引，k为要检查的位数 */
  1. static void real_radix_exchange_sort(int *array, int left, int right, int k)
  2. {
  3.     /* radix sort的必需条件 */
  4.     if (right > left && k >= 0) {
  5.         int i, j, t;
  6.         i = left;
  7.         j = right;
  8.         
  9.         while (j > i) {
  10.             /* 找到第一个k位为1的数值 */
  11.             while (GET_BITS(array[i], k, 1) == 0 && i < j) ++i;
  12.             /* 找到第一个k位为0的数值*/
  13.             while (GET_BITS(array[j], k, 1) == 1 && j > i) --j;
             
             /* 交换两个数值，保证该位为0的数值在该位为1的数组的前面 */
             if (i != j) {
  1.                  t = array[i];
  2.                  array[i] = array[j];
  3.                  array[j] = t;
  4.             }
  5.         }

         /* 确保left到i的数值都是k位为0的数值，然后继续radix exchange sort */  
  1.         if (GET_BITS(array[i], k, 1) == l) --i;
  2.         real_radix_exchange_sort(array, left, i, k-1);
  3.         /* 确保j到right的数值都是k位为1的数组，然后继续radix exchange sort*/ 
  4.         if (GET_BITS(array[j], k, 1) == 0) ++j;
  5.         real_radix_exchange_sort(array, j, right, k-1);
  6.     }
  7. }
下面在看看Algorithm In C中的实现方法，与上面的略有不同：
  1. static void real_radix_exchange_sort(int *array, int left, int right, int k)
  2. {
  3.     if (right > left && k >= 0) {
  4.         int i, j, t;
  5.         i = left;
  6.         j = right;
  7.         
  8.         while (j > i) {
  9.             while (GET_BITS(array[i], k, 1) == 0 && i < j)    ++i;
  10.             while (GET_BITS(array[j], k, 1) == 1 && j > i) --j;
  11.             t = array[i];
  12.             array[i] = array[j];
  13.             array[j] = t;
  14.         }
  15.         if (GET_BITS(array[j], k, 1) == 0) j++;
  16.         real_radix_exchange_sort(array, left, j-1, k-1);
  17.         real_radix_exchange_sort(array, j, right, k-1);
  18.     }
  19. }
关键的不同的地方就在于上面红色的三行代码。

在划分子问题的时候，我使用了i和j两个变量，而上面的代码只使用了一个变量j。这样就可以减少一个条件判断。造成这个问题的原因，主要是想问题的思路不同。我在考虑这个问题时，想着i是用来遍历该位为0的索引，而j是用来遍历该位为1的索引。这样就可以将原问题划分为2个子问题。一个是使用i来限制的该位为0的数值的集合，另一个是使用j来限制该位为1的数值的集合。这里其实已经有问题了。如果真的同时需要i和j的话，那么说明原来的数组应该被划分为3个子问题了。这无疑是不正确的。

正确的结果是将原有的数组划分为两个子数组。其实一次radix exchange结束后，即该while循环结束时，i和j很自然是相等的。但是我们无法保证循环结束时，array[i]是该位为0的数值，或者array[j]是该位为1的数值。所以，才有后面的条件判断。这就是为什么Algorithm In C会写上面三行代码。

在完成这个排序方法后，我不得不再次感叹递归的强大，以及Divide & Conquer思想。

注：
1. Algorithm In C：Chapter 10

上一篇：程序员的职业发展
下一篇：Hadoop基本流程与应用开发