基数排序（Radix Sort）

 

计数排序的缺点很明显，需要额外的空间C来作为计数数组，虽然时间复杂度为O(n+k)，但当输入序列里元素取值很大的时侯，如k=O(n²)，时，此时时间复杂度已经达到n²数量级了，空间的消耗也是让人无法承受的。这里介绍一种另一种线性排序算法——基数排序，可以应对数值很大的情况。

 

基数排序，即一个数位一个数位地进行排序，平常生活中我们经常使用的一种算法思想：如要对一个日期进行排序，日期中由年、月、日组成的，对于这个问题，我们经常使用的是先比较年份，如果相同再比较月份，如果还相同就比较日。

 

同理，我们比较一组数，也可以采取这种思想。例如我们使用这种思想对下面四个数进行排序：123、312、245、531，第一次按百位排序：123、245、312、531；第二次按十位排序：312、123、531、245；第三次按个位数排序：531、312、123、245。咦？为什么最后排出来的结果并不是预期的那样？原因是我们从高位开始排序，已经差不多整体有序之后，再到低位时，又全部被打乱了。如果我们之后这样做就不会乱了：高位相同的数，再将它们的低位进行排序….不过这个实现一起比较困难一些。

这里，我们换成从最低有效位到最高有效位进行排序，那么还是上面那个例子：

   个位 =>  十位 =>  百位

   531      312      123

   312      123      245

   123      531      312

   245      245      531

可以看到结果正确。通俗地讲，之所以先排低位再排高位，是因为越是后排的数位，其对结果次序的影响越大，很显然是高位比低位对数的大小影响大！

这里再给出一个简单的证明过程：

假定一组序列低t-1位已经排序好了，现在我们按照第t位进行排序。我们只需证明对于任意两个数来说，按照第t位排序之后其相对位置正确。任意两个数这时有两种情况：

1）它们第t位相同，那么此时如果我们保持它们位置的稳定性，那么它们最后仍然有序；

2）它们第t位不同，按照第t位排序之后就有序了。

所以，即证明了基数排序的正确性。从这里我们可以看出非常关键的一点——排序必需要稳定！很快就想到使用前面说过的计数排序算法！

那么可以得出计数排序的伪代码为:

 

radixSort(A,d)   //d为A中元素最多的位数  
    for i=1 to d  
       do use a stable sort to sort array A on digit i  

 可以得到时间复杂度为O(d(n+k)); 当d为常数、k=O(n)时，基数排序有线性的运行时间的。

 

 

更具体更普遍一点的算法：

/* n为待排序数组A的元素个数，B为按位计数排序后暂存数据的辅助数组，C则是计数数组，b为最大元素的长度（bit位数），r为每个数位的长度（即计数排序以2**r进制） */ 

 

radixSort(int A[], int B[], int C[], int n, int b, int r)  
       m=b/r;     //m是最大的位数  
       for  i=0 to m-1 do  
              for j=0 to r-1 do  
                     C[j] = 0;          //计数数组清零  
              for j=0 to n-1 do  
                     C[(A[j]/t)%2**r]++;    //C[j]表示等于j的元素个数  
              for j=1 to r-1 do  
                     C[j] = C[j]+C[j-1];     //C[j]表示等于或者小于j的元素个数  
              for j=n-1 downto 0 do  
                     B[--C[(A[j]/t)%2**r]]=A[j];    //计数排序  
              for j=0 to n-1 do  
                     A[j] = B[j];  
          t = t*2**r;  

基数排序比较适合对取值很大的数进行排序，也可用来对字符串进行排序。

 

 

最终代码如下：（计数排序部分尚未优化）

import java.util.Arrays;
/**
 * @author
 */
public class RadixSorter {

    public static boolean USE_LINK = true;

    /**
     * 
     * @param keys
     * @param from
     * @param len
     * @param radix
     *            key's radix
     * @param d
     *            how many sub keys should one key divide to
     */
    public void sort(int[] keys, int from, int len, int radix, int d) {
        if (USE_LINK) {
            linkRadixSort(keys, from, len, radix, d);
        } else {
            arrayRadixSort(keys, from, len, radix, d);
        }
    }

    private final void arrayRadixSort(int[] keys, int from, int len, 
            int radix, int d) {
        int[] temporary = new int[len];
        int[] count = new int[radix];
        int R = 1;

        for (int i = 0; i < d; i++) {
            System.arraycopy(keys, from, temporary, 0, len);
            Arrays.fill(count, 0);
            for (int k = 0; k < len; k++) {
                // 当前要排的位
                int subkey = (temporary[k] / R) % radix;
                count[subkey]++;
            }

            /* 与计数排序相同 */
            for (int j = 1; j < radix; j++) {
                count[j] += count[j - 1];
            }

            for (int m = len - 1; m >= 0; m--) {
                int subkey = (temporary[m] / R) % radix;
                --count[subkey];
                // temporary 存储着某位已经排好序的数组
                keys[from + count[subkey]] = temporary[m];
            }
            R *= radix;
        }
    }

    private static class LinkQueue {
        int head = -1;
        int tail = -1;
    }

    private final void linkRadixSort(int[] keys, int from, int len, 
            int radix, int d) {

        int[] nexts = new int[len];

        LinkQueue[] queues = new LinkQueue[radix];
        for (int i = 0; i < radix; i++) {
            queues[i] = new LinkQueue();
        }

        for (int i = 0; i < len - 1; i++) {
            nexts[i] = i + 1;
        }
        nexts[len - 1] = -1;

        int first = 0;
        for (int i = 0; i < d; i++) {
            linkRadixSortDistribute(keys, from, len, radix, i, nexts, queues, first);
            first = linkRadixSortCollect(keys, from, len, radix, i, nexts, queues);
        }

        int[] tmps = new int[len];
        int k = 0;
        while (first != -1) {

            tmps[k++] = keys[from + first];
            first = nexts[first];
        }
        System.arraycopy(tmps, 0, keys, from, len);
    }

    private final void linkRadixSortDistribute(int[] keys, int from, int len, 
            int radix, int d, int[] nexts, LinkQueue[] queues, int first) {

        for (int i = 0; i < radix; i++) {
            queues[i].head = queues[i].tail = -1;
        }

        while (first != -1) {
            int val = keys[from + first];
            for (int j = 0; j < d; j++) {
                val /= radix;
            }
            val = val % radix;

            if (queues[val].head == -1) {
                queues[val].head = first;
            } else {
                nexts[queues[val].tail] = first;
            }

            queues[val].tail = first;
            first = nexts[first];
        }
    }

    private int linkRadixSortCollect(int[] keys, int from, int len, int radix, 
            int d, int[] nexts, LinkQueue[] queues) {
        int first = 0;
        int last = 0;
        int fromQueue = 0;

        for (; (fromQueue < radix - 1) && (queues[fromQueue].head == -1); 
                fromQueue++) {
            ;
        }

        first = queues[fromQueue].head;
        last = queues[fromQueue].tail;

        while (fromQueue < radix - 1 && queues[fromQueue].head != -1) {
            fromQueue += 1;
            for (; (fromQueue < radix - 1) && (queues[fromQueue].head == -1); 
                    fromQueue++) {
                ;
            }

            nexts[last] = queues[fromQueue].head;
            last = queues[fromQueue].tail;
        }
        if (last != -1) {
            nexts[last] = -1;
        }
        return first;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] a = { 1, 4, 8, 3, 2, 9, 5, 0, 7, 6, 9, 10, 9, 135, 14, 15, 11, 
                222222222, 1111111111, 12, 17, 45, 16 };
        USE_LINK = false;
        RadixSorter sorter = new RadixSorter();
        sorter.sort(a, 0, a.length, 10, 10);
        System.out.println(Arrays.toString(a));
    }
}

 

基数排序的缺点:

 

不呈现时空局部性，因为在按位对每个数进行排序的过程中，一个数的位置可能发生巨大的变化，所以不能充分利用现代机器缓存提供的优势。同时计数排序作为中间稳定排序的话，不具有原地排序的特点，当内存容量比较宝贵的时候，还是有待商榷。