分配排序，常见的有三种，计数排序和桶排序和基数排序，他们的时间复杂度最好都是O(dn), d是指数组中最大的数
计数排序、桶排序和基数排序都用了一种方法，把想要排序的数据放到桶子里，再进行排序，这是一种用空间换取效率的方法。
首先讲计数排序，是一种执行效率非常高的算法，缺点是应用限制太多，只能用于正整数。
计数排序思想很简单，就像中国好声音那样，评委举了多少张10分的牌，就计算得到多少次10分，再按照那些牌是举过的，从低到高遍历，举多少次就输出多少次。
以下面的数组A[7]={2,3,5,6,1,10,100}为例:
我们知道了大概排序的策略，但是应该分多少个张牌才行呢？为了不漏，必须每个分数分一张牌。
所以我们只能从最大数处确认需要分配多少张牌。
获取最大数:
int Getmaxnum(int *arr,int n) { int max=arr[0]; for(int i=0;i<n;i++) if(arr[i]>max) max=arr[i]; return max; }关键代码: void countsort(int *arr,int n) { int max=Getmaxnum(arr,n); int *a=new int[max+1]; for(int i=0;i<max+1;i++) a[i]=0; for( i=0;i<n;i++) a[arr[i]]++; //第i张牌加1 int j=0; for(i=0;i<max+1;i++) { for(int k=a[i];k!=0;k--)//把所有的牌按照出现次数存起来 { arr[j]=i; j++; } } delete []a; }下面对于20000个数的排序情况:细心的朋友可以看到这个时间比之前的快了很多，这个要澄清一下，前面的占用时间比较多的原因是计算时间把printf的时间算进去了，其实一般都是0.01秒左右计算完2000个数据的排序的了，在我这台电脑。
下面讲桶排序:
桶排序，的思想是把待排的数据按照某中映射到指定的区间，就是桶，举个例子，我们在上体育课回收哑铃的时候是按照哑铃的重量进行回收的，同一个型号的放到同一个桶，我们排序仅仅需要从桶的编号排序便可(从型号到桶编号说的就是这种映射)
在这里我们建立一个映射如下：把小于10的放到0号桶，10到100的放到1号桶，再对桶里面的采用我们常见的排序方法，可以用插入排序等等。
但是一个桶怎么装的下那么多数据呢，这里我们采用链表的方式，来访问同一个同的数据。所以桶的个数的选择是看数据的大小，我们这里采用映射是m(桶编号)=n(数组的值)/10，则0-10的数据，采用1个桶就够了，免的浪费空间。
关键代码:
typedef struct Node { int key; struct Node *next; }KeyNode; void bucketsort(int *arr, int n,int bucketsize) { //arr为数组首地址，n为数组元素,bucketsize为桶的个数 KeyNode **bucket=(KeyNode**)malloc(sizeof(KeyNode*)*bucketsize); for(int i=0;i<bucketsize;i++) { //初始化每一个桶 bucket[i]=(KeyNode*)malloc(sizeof(KeyNode)); bucket[i]->key=0; bucket[i]->next=NULL; } for(int j=0;j<n;j++) { KeyNode *node=(KeyNode*)malloc(sizeof(KeyNode)); node->key=arr[j]; node->next=NULL; int index=arr[j]/10; KeyNode *p=bucket[index]; //桶中链表的头结点 if(p->key==0) { bucket[index]->next=node; bucket[index]->key++; } else { //对同一个桶的数据采用插入排序 while(p->next!=NULL&&p->next->key<=node->key) p=p->next; node->next=p->next; p->next=node; bucket[index]->key++; } } //输出所有桶中的数据 for(int k=0;k<bucketsize;k++) for(KeyNode *N=bucket[k]->next;N!=NULL;N=N->next) printf("%d\n",N->key); }20000个数据的执行时间如下:
一口气讲了两种排序，下面继续讲基数排序
为什么叫做基数排序呢，因为我们要通过获取每一种进制他们的基数进行获取每一位的数值。，例如10进制的基数就是10.
基数排序的思想呢，是从数的低位开始对整个数组排序，首先排个位数，再排十位数，再排百位数，分别把每位数存到桶里面，收集，直接排到最高位，便可得有序数组。举个例子，例如我要排列一组数A[7]={110,123,301,20,10,1,2,11}
110，123，301，20，10，1，2，11，我们对它进行修饰一下，变成110，123，301，020，010，001，002，011
个位数:
0号桶 1号桶 2号桶 3号桶
110 301 002 123
020 001
010 011
把按照个位分配好的从零0号桶开始收集得，110，020，010，301，001，011，002，123
十位数:
0号桶 1号桶 2号桶 3号桶
301 110 020
001 010 123
002 011
把按照10位分配好的从零0号桶开始收集得，301，001，002，110，010，011，020,123
百位数:
0号桶 1号桶 2号桶 3号桶
001 110 301
002 123
010
011
020
把按照百位分配好的从零0号桶开始收集得，001，002，010，011，020，110，123，301
得出有序数组。
因此我们要把每个数的每个分位进行取出来
求每个分位的函数：
int GetNumPos(int num,int pos) { int temp=1; for(int i=0;i<pos;i++) temp*=10; return (num/temp); }关键代码 : #define LEN10 10 #define KEYNUM 10 void Radixsort(int *arr,int n) { int *bucket[LEN10]; for(int i=0;i<LEN10;i++) { bucket[i]=(int*)malloc(sizeof(int)*(n+1)); bucket[i][0]=0; } for(int pos=1;pos<KEYNUM;pos++) { for(int i=0;i<n;i++) { int num=GetNumPos(arr[i],pos); int index=++bucket[num][0]; //分配到指定编号的桶 bucket[num][index]=arr[i]; } for(int k=0,j=0;k<LEN10;k++) { //重新收集分配好的数据 for(int c=1;c<=bucket[k][0];c++) arr[j++]=bucket[k][c]; bucket[k][0]=0; } } } 20000个数的排序时间情况如下:
由此看出最简单和最快的是计数排序，最复杂的是桶排序，但是他们都是属于分配排序的一种，因为受限制太多，因此用的比较少。
