基数排序(Radix Sort)

计数排序和桶排序都只是在研究一个关键字的排序，现在我们来讨论有多个关键字的排序问题。

基数排序 vs 计数排序 vs 桶排序

基数排序有两种方法：

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

• 基数排序：根据键值的每位数字来分配桶；
• 计数排序：每个桶只存储单一键值；
• 桶排序：每个桶存储一定范围的数值

关键概念

假设我们有一些二元组(a,b)，要对它们进行以a为首要关键字，b的次要关键字的排序。我们可以先把它们先按照首要关键字排序，分成首要关键字相同的若干堆。然后，在按照次要关键值分别对每一堆进行单独排序。最后再把这些堆串连到一起，使首要关键字较小的一堆排在上面。按这种方式的基数排序称为MSD(Most Significant Dight)排序。

第二种方式是从最低有效关键字开始排序，称为LSD(Least Significant Dight)排序。首先对所有的数据按照次要关键字排序，然后对所有的数据按照首要关键字排序。要注意的是，使用的排序算法必须是稳定的，否则就会取消前一次排序的结果。由于不需要分堆对每堆单独排序，LSD方法往往比MSD简单而开销小。下文介绍的方法全部是基于LSD的。

通常，基数排序要用到计数排序或者桶排序。使用计数排序时，需要的是Order数组。使用桶排序时，可以用链表的方法直接求出排序后的顺序。下面是一段用桶排序对二元组基数排序的程序：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
struct data
{
    int key[2];
};
struct linklist
{
    linklist *next;
    data value;
    linklist(data v,linklist *n):value(v),next(n){}
    ~linklist() {if (next) delete next;}
};
void BucketSort(data *A,int N,int K,int y)
{
    linklist *Bucket[101],*p;//建立桶
    int i,j,k,M;
    M=K/100+1;
    memset(Bucket,0,sizeof(Bucket));
    for (i=1;i<=N;i++)
    {
        k=A[i].key[y]/M; //把A中的每个元素按照的范围值放入对应桶中
        Bucket[k]=new linklist(A[i],Bucket[k]);
    }
    for (k=j=0;k<=100;k++)
    {
        for (p=Bucket[k];p;p=p->next) j++;
        for (p=Bucket[k],i=1;p;p=p->next,i++)
            A[j-i+1]=p->value; //把桶中每个元素取出
        delete Bucket[k];
    }
}
void RadixSort(data *A,int N,int K)
{
    for (int j=1;j>=0;j--) //从低优先到高优先 LSD
        BucketSort(A,N,K,j);
}
int main()
{
    int N=100,K=1000,i;
    data *A=new data[N+1];
    for (i=1;i<=N;i++)
    {
        A[i].key[0]=rand()%K+1;
        A[i].key[1]=rand()%K+1;
    }
    RadixSort(A,N,K);
    for (i=1;i<=N;i++)
        printf("(%d,%d) ",A[i].key[0],A[i].key[1]);
    printf("\n");
    return 0;
}

基数排序是一种用在老式穿卡机上的算法。一张卡片有80列，每列可在12个位置中的任一处穿孔。排序器可被机械地"程序化"以检查每一迭卡片中的某一列，再根据穿孔的位置将它们分放12个盒子里。这样，操作员就可逐个地把它们收集起来。其中第一个位置穿孔的放在最上面，第二个位置穿孔的其次，等等。

对于一个位数有限的十进制数，我们可以把它看作一个多元组，从高位到低位关键字重要程度依次递减。可以使用基数排序对一些位数有限的十进制数排序。

对整数排序

对于排序整数，排序过程可以通过这个动图查看

img

public class RadixSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxDigit = getMaxDigit(arr);
        return radixSort(arr, maxDigit);
    }

    /**
     * 获取最高位数
     */
    private int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }

    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    protected int getNumLenght(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }

    private int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
            int[][] counter = new int[mod * 2][0];

            for (int j = 0; j < arr.length; j++) {
                int bucket = ((arr[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    arr[pos++] = value;
                }
            }
        }

        return arr;
    }

    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}