基数排序

基数排序

使用例子来讲基数排序是最直观的。假设有10个0~999之间的十进值数，分别是64 8 216 512 27 729 0 1 343 125，对这几个数如何使用基数排序呢？基数排序顾名思义跟基数有关系，这里的数都是十进制的，所以基数Radix = 10。十进制数在某一位上最多有10个不同可能，比如说个位上的数，只能是0~9之间的某一个。假如这些数先按个位上的数的大小排序，那就可以设置10个桶，分别用来装这些可能数。但是每个桶只能装一个数，如果有两个数个位上的数是相同的怎么办？我们可以把这两个数放到表里面，桶保存的是这个表，而不再是某个数了。这样把这10个数都装完之后，按顺序打印桶里的数，就得到了按个位排序的顺序。同理，我们再用十位，百位来排序，最后一趟排序就能得到正确的结果。在这个排序过程中，按地位排序能得到正确的结果，但是如果按高位排序则不能。

描述一下按基数排序的步骤：

（1）首先设置基数大小的桶，桶里的每个元素都是用来保存表的；

（2）先按个位排序，遍历待排序序列，如果它个位上的数是0，则装进第0个桶里的链表里，如果是1，则装进第1个桶里的链表....

（3）按顺序收集各个桶里的数，这样得到的新序列就是按个位排序的结果

（4）在按个位排序的结果上，再分别用十位上的数排序，过程同上

（5）收集按十位排序的结果

（6）接着按百位、千位，直到最高位排序，最后一趟收集的结果就是排序的正确序列。

我们用图来形象的展示基数排序过程，首先是设置10个桶，初始时h[i]和t[i]都指向这些桶，其中，h[i]始终指向着这个桶，t[i]则指向该桶链表的最后一个元素，方便插入元素，为了方便，我使用了头结点，h[i]就是头结点。待排序序列表L，一次排序完成后，L收集各个桶里表，收集顺序是：

（1）L指向第一个非空桶的链表的第一个元素，该链表的表尾是t[i]

（2）t[i]->next是下一个非空桶的链表的第一个元素，然后依次将非空的桶按首尾顺序连接起来。

然后按十位排序，其过程如下图

接着按百位排序，过程省略。给出示意性代码，分别给出了链表L和桶都使用头结点和都不使用头结点的代码，使用头结点要注意头结点的复用问题，不使用同节点在要考虑第一个元素的特殊情况。首先是声明：

#define Radix 10 //基数

/********对链表的定义*********/
typedef int ElementType;

typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

struct Node {
    ElementType element;
    Position next;
};
/********定义结束************/

Position h[Radix];//保存每个表的头元素
Position t[Radix];//保存每个表的尾元素

/*获取某个数(n)的某个位(place)上的值*/
int getPlace(int n,int place) {
    int div = 1;
    int i = 0;
    for(i = 1; i < place; i++)
        div *= Radix;
    return (n / div) % Radix;
}

链表L和桶都使用头结点的情况：

/*初始化保存表头的数组*/
void initH() {
    int i = 0;
    for(; i <Radix; i++) {
          h[i] = malloc(sizeof(struct Node));
          h[i]->next = NULL;
    }
}

/*是一趟基数排序，place是位，L存放待排序数据*/
List sort(int place,List L) {
    int i = 0;
    //每次排序前都要清除桶与前一次排序的联系
    for(i = 0; i < Radix; i++) {
         t[i] = h[i];
         t[i]->next = NULL;
    }
    //为了复用头结点，需要先保存起来，也就是说在整个基数排序过程中，它始终是链表的头结点
    Position head = L;

    Position p = NULL;
    L = L->next;//第一个元素
    while(L != NULL) {
        p = L;
        L = L->next;
        int index = getPlace(p->element,place);
        p->next = NULL;

        t[index]->next = p;
        t[index] = p;
    }


    //复用头结点
    L = head;
    L->next = NULL;
    Position q = L;
    //进行合并
    for(i = 0; i < Radix; i++) {
        if(h[i]->next != NULL) {
           q->next = h[i]->next;
           q = t[i];
        }
    }

    return L;
}

不使用头结点的代码：

/*初始化桶*/
void InitHT() {
    int i = 0;
    for(i = 0; i < Radix; i++) {
        h[i] = t[i] = NULL;
    }
}

List sortNoHead(int place,List L) {
    //每次排序前都需要初始化桶，这个很关键，要清除它与上次的关系
    InitHT();
    Position p = NULL;

    while(L != NULL) {
        //当前正在处理的节点
        p = L;
        //位置很重要，如果放到最后的话，L当前指向的节点已经改变了
        L = L->next;
        //这句话很重要，切断它与原来链表的联系
        p->next = NULL;
        //当前位上的数
        int index = getPlace(p->element,place);
        //如果是该表的第一个数，就将h[index]和t[index]指向它，否则，将它加入链表后面
        if(t[index] == NULL) {
            h[index] = t[index] = p;
        }else {
            t[index]->next = p;
            t[index] = p;
        }
    }

    //合并
    Position tmp = NULL;

    int i = 0;
    for(i = 0; i < Radix; i++) {
        if(h[i] != NULL) {
            //不适用头结点，则要考虑tmp和L第一次指向非空表时的特殊情况
            if(tmp == NULL) {
                tmp = h[i];
                L = h[i];
            }
            else {
               tmp->next = h[i];
               tmp = t[i];
            }

        }
    }

    return L;
}

以上代码是用C语言写的，C的参数传递方式是值传递，我们看到如果把链表L传到函数里面，在函数里面使用的是L的副本L'，L'指向的内存发生了变化，所以我们必须要返回L'。

时间复杂度分析

一趟基数排序的过程：把N个元素分别放到不同的桶里需要O(N)，之后需要收集各个桶，重新组成链表，总共有Radix个桶，需要时间O(Radix)。所以一趟排序的时间是：O(N + Radix)。如果待排序序列的最高有P位，也就是需要P趟排序，所以总时间是：

O(P(N + Radix))，N待排序元素个数，Radix桶数，P排序的趟数。

快速排序的时间复杂度是O(NlogN)，看上去基数排序的趟数要少一下，但是快速排序每一趟执行的时间要长得多，快速排序通常可以比基数排序更好的利用硬件缓存,logN的因子不都那么大）。如果待排序序列中有很大的数，其余的则很小，这样就不太好了，而且基数排序还有保存链表的附加开销。有一点需要注意：基数排序必须是稳定的。