学步园

一、基数排序的基本思想：排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶：O(n)。

二、最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。
      最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。

#include "stdio.h"<br /> #include "stdlib.h"<br /> int main(void)<br /> {<br /> int data[10]={73,22,93,43,55,14,28,65,39,81};<br /> int temp[10][10]={0};<br /> int order[10]={0};<br /> int i,j,k,n,lsd;<br /> k=0;n=1;<br /> printf("排序前: ");<br /> for (i=0;i<10;i++)<br /> printf("%d ",data[i]);<br /> putchar('/n');<br /> while (n<=10)<br /> {<br /> for (i=0;i<10;i++)<br /> {<br /> lsd=((data[i]/n)%10);<br /> temp[lsd][order[lsd]]=data[i];<br /> order[lsd]++;<br /> }<br /> printf("/n重新排列: ");<br /> for (i=0;i<10;i++)<br /> {<br /> if(order[i]!=0)<br /> for (j=0;j<order[i];j++)<br /> {<br /> data[k]=temp[i][j];<br /> printf("%d ",data[k]);<br /> k++;<br /> }<br /> order[i]=0;<br /> }<br /> n*=10;<br /> k=0;<br /> }<br /> printf("/n");<br /> printf("/n排序后: ");<br /> for(i=0;i<10;i++)<br /> printf("%d ",data[i]);<br /> printf("/n");<br /> system("pause");<br /> return 0;<br /> }