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的数值分别检查下一位，直至检查到最低位，这时就完成了排序。根据这个思想，很自然就可以想到需要用递归来实现。

//得到从k位开始的n个bits
#define GET_BITS(bytes, k, n)     ((bytes>>k) & ~((~0)<<n))


void radix_exchange_sort(int *array, int size)
{
    real_radix_exchange_sort(array, 0, size-1, 31);
}

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

         /* 确保left到i的数值都是k位为0的数值，然后继续radix exchange sort */	 
        if (GET_BITS(array[i], k, 1) == l) --i;
        real_radix_exchange_sort(array, left, i, k-1);
        /* 确保j到right的数值都是k位为1的数组，然后继续radix exchange sort*/ 
        if (GET_BITS(array[j], k, 1) == 0) ++j;
        real_radix_exchange_sort(array, j, right, k-1);
    }
}

下面在看看Algorithm In C中的实现方法，与上面的略有不同：

static void real_radix_exchange_sort(int *array, int left, int right, int k)
{
    if (right > left && k >= 0) {
        int i, j, t;
        i = left;
        j = right;
        
        while (j > i) {
            while (GET_BITS(array[i], k, 1) == 0 && i < j)    ++i;
            while (GET_BITS(array[j], k, 1) == 1 && j > i) --j;
            t = array[i];
            array[i] = array[j];
            array[j] = t;
        }
        if (GET_BITS(array[j], k, 1) == 0) j++;
        real_radix_exchange_sort(array, left, j-1, k-1);
        real_radix_exchange_sort(array, j, right, k-1);
    }
}

关键的不同的地方就在于上面红色的三行代码。

在划分子问题的时候，我使用了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思想。