基数排序

基数排序是把一个逻辑关键字看成是由多个关键字组合而成的，并且一步一步地按每个关键字排号顺序，如把这些关键字记为：$K^0$,$K^1$,…,$K^{r-1}$,其中$K^0$为该记录中最高有效关键字，而$K^{r-1}$为最低有效关键字。如果从最高有效关键字开始排序成为MSD排序，如果从最低有效关键字开始排序成为LSD排序。
例如,一个整数由若干位组成，且各位都有次序的，从而使其最右边的数字为是最低有效位，而最左边的数字位是最高有效位，比如整数的范围为0<=K<=999,那么就可以使用LSD或MSD方法进行排序，此时有三个关键字($K^0$,$K^1$,$k^2$),其中$k^0$是百位上的数字，$k^1$为十位上的数字，而$k^2$为个位上的数字，由于所有的关键字都属于0=<$k^i$<=9范围，所以对每个关键字的排序都只需10个箱子。
假设输入序列为(179,208,306,93,859,984,55,9,271,33),则技术排序如下：

代码实现：

#include<stdio.h>
#define MAX_SIZE 100
#define MAX_DIGIT 3
#define RADX_SIZE 10
typedef struct list_node *list_pointer;
typedef struct list_node
{
   int key[MAX_DIGIT];
   list_pointer link;
};
//基数LSD排序
list_pointer radix_sort(list_pointer ptr)
{
   list_pointer front[RADX_SIZE],rear[RADX_SIZE];
   int i,j,digit;
   //从最低关键字进行排序
   for(i=MAX_DIGIT;i>=0;i--)
   {
      for(j=0;j<RADX_SIZE;j++)
         front[j]=rear[j]=NULL;
      while(ptr)
      {
         //获取值作为箱子的索引
         digit=ptr->key[i];
         //是否第一个元素
         if(!front[digit])
            front[digit]=ptr;
         else
            rear[digit]->link=ptr;
         rear[digit]=ptr;
         ptr=ptr->link;
      }
      ptr=NULL;
      //寻找第一个元素不为空的最小箱子索引，为下一个关键字排序做准备
      for(j=RADX_SIZE-1;j>=0;j--)
      {
         if(front[j])
         {
            rear[j]->link=ptr;ptr=front[j];
         }
      }
   }
   return ptr;
}

函数radix_sort对记录进行MAX_DIGIT遍扫描，每遍的处理时间为O(RADX_SIXE+n)，所以，总的计算时间为O(MAX_DIGIT(RADIX_SIXE+n)).