C语言，基数排序(149,138,165,197,176,113,127)？

基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

以LSD为例，假设原来有一串数值如下所示：

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：

0

1 81

2 22

3 73 93 43

4 14

5 55 65

6

7

8 28

9 39

接下来将这些桶子中的数值重新串接起来，成为以下的数列：

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接着再进行一次分配，这次是根据十位数来分配：

0

1 14

2 22 28

3 39

4 43

5 55

6 65

7 73

8 81

9 93

接下来将这些桶子中的数值重新串接起来，成为以下的数列：

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。

LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好，MSD的方式恰与LSD相反，是由高位数为基底开始进行分配，其他的演算方式则都是相同。

/*有一种排序方法叫Radix Sort,就是针对这种多关键字的排序的

时间复杂度线性的，但是有个缺点就是必须知道关键字的范围，不知道题主的关键字范围是多少？

好吧，假设我的关键字最多有100个，基数最大不超过999

程序如下：   */

//Radix Sort算法，采取LSD（低位优先）

#include<stdio.h>

#include<stdlib.h>

#define KEYNUM 100                 //关键字的最大个数

#define RADIX 1000                 //基数的范围是0-RADIX-1

typedef struct Node

{

  int ele[KEYNUM+1]

  struct Node *next

} Node

Node *e[RADIX],*f[RADIX]         //链队列的首指针和尾指针表

void init(Node* head,int n,int m)   //初始化输入链表

{

  int i,j

  Node *p,*q=head

  for(i=0i<ni++)

  {

      p=(Node*)malloc(sizeof(Node))

      if(!p)

          return

      for(j=1j<=mj++)

          scanf("%d",&p->ele[j])

      p->next=NULL

      q->next=p

      q=q->next

  }

}

void distribute(Node* head,int locate,int r)      //进行Radix排序

{

  Node *p,*q

  int i

  while(head->next!=NULL)

  {

      q=head->next

      head->next=q->next

      q->next=NULL

      p=f[q->ele[locate]]

      while(p->next!=NULL)

          p=p->next

      p->next=q

      e[q->ele[locate]]->next=q

  }

  p=head

  for(i=0i<=ri++)

  {

      while(f[i]->next!=e[i]->next)

      {

          q=f[i]->next

          f[i]->next=q->next

          q->next=NULL

          p->next=q

          p=p->next

      }

      q=f[i]->next

      if(q)

      {

          f[i]->next=q->next

          q->next=NULL

          p->next=q

          p=p->next

      }

      f[i]->next=e[i]->next=NULL

  }

}

void display(Node* head,int m)              //显示链表各个节点

{

  int i

  Node* p=head->next

  if(!head)

      return

  while(p)

  {

      for(i=1i<=mi++)

          printf("%d ",p->ele[i])

      printf("\n")

      p=p->next

  }

}

void Delete(Node* head)                        //释放链表节点

{

  Node *p

  if(!head)

      return

  while(head->next)

  {

      p=head->next

      head->next=p->next

      free(p)

  }

}

int main()

{

  Node* head

  int n,m,r,i

  for(i=0i<RADIXi++)                           //初始化首尾指针指向空指针

  {

      f[i]=(Node*)malloc(sizeof(Node))

      e[i]=(Node*)malloc(sizeof(Node))

      if(!f[i]||!e[i])

          exit(1)

      f[i]->next=e[i]->next=NULL

  }

  head=(Node*)malloc(sizeof(Node))

  if(!head)

      return 1

  printf("待排序个数以及关键字的个数：")

  scanf("%d%d",&n,&m)

  printf("输入数据：\n")

  init(head,n,m)

  printf("输入基数范围0-n：")

  scanf("%d",&r)

  for(i=mi>=1i--)

      distribute(head,i,r)                             //从低位到高位进行Radix排序

  display(head,m)

  for(i=0i<RADIXi++)                            //释放首尾指针数组

  {

      free(f[i])

      free(e[i])

  }

  Delete(head)

  free(head)

  return 0

}

题主的答案：

更复杂的情况：

---