1、计数排序

(1)、算法思想

是一组在特定范围内的整数，在线性时间内排序，比nlog(n)更快的排序算法；

较小范围内是比较好的排序算法，如果很大是很差的排序算法；

可以解决重复元素的出现的排序算法；

(2)、代码实现

#include<stdio.h>voidcountSort(int*a,intcount);voidshowArray(int*a,intcount);voidshowArray(int*a,intcount){inti;for(i=0;i<count;i++){printf("%d",a[i]);}printf("\n");}voidcountSort(int*a,intcount){intb[10]={0};int*c;inti;c=(int*)malloc(sizeof(int)*count);for(i=0;i<count;i++){b[a[i]]++;}for(i=1;i<10;i++){b[i]+=b[i-1];}for(i=count-1;i>=0;i--){c[b[a[i]]-1]=a[i];b[a[i]]--;}for(i=0;i<count;i++){a[i]=c[i];}free(c);}voidmain(void){inta[]={2,4,7,2,1,0,9};intcount=sizeof(a)/sizeof(int);countSort(a,count);showArray(a,count);}

(3)、结果截图

(4)、算法分析：

计数排序优点：稳定性(一个稳定性算法保证了相等元素的顺序)；

时间复杂度：O(n)；


2、基数排序

(1)、算法思想

i、从最后一位(低位-->高位)开始排序，并且的是稳定的排序算法(辅助算法：计数排序)，整体思想：按位排序；

ii、在进行基数排序时，从个位--->十位--->百位......每取一位时，分别进行计数排序，传的参数：位、要排序的总数、新的结果、辅助空间(开辟10个元素的空间)、原先数组；利用位和辅助空间，将原先数组的值放入新的结果空间中即可；(位的顺序与原先结果的顺序保持一致)!!!

iii、基数排序只要知道最大数是几位，进行几次排序即可；

(2)、代码实现

#include<stdio.h>#include<malloc.h>voidradixSort(int*a,intcount);voidcountSort(int*bitNumber,intcount,int*newA,int*c,int*a);voidshowArray(int*a,intcount);voidshowArray(int*a,intcount){inti;for(i=0;i<count;i++){printf("%d",a[i]);}printf("\n");}voidcountSort(int*bitNumber,intcount,int*newA,int*c,int*a){inti;//从个位-->十位-->百位,每一次调用这个函数,辅助空间都必须初始化为0;for(i=0;i<10;i++){c[i]=0;}for(i=0;i<count;i++){c[bitNumber[i]]++;}for(i=1;i<10;i++){c[i]+=c[i-1];}for(i=count-1;i>=0;i--){newA[c[bitNumber[i]]-1]=a[i];//a[i]与原先所取的位顺序一致c[bitNumber[i]]--;}}voidradixSort(int*a,intcount){int*bitNumber;int*newA;intc[10]={0};inti;//个位进行排序bitNumber=(int*)malloc(sizeof(int)*count);newA=(int*)malloc(sizeof(int)*count);for(i=0;i<count;i++){bitNumber[i]=a[i]%10;}countSort(bitNumber,count,newA,c,a);//bitNumber:代表要排的数字;newA:代表最终排行的新空间//c:代表辅助空间a:代表原先数字for(i=0;i<count;i++){a[i]=newA[i];}//十位进行排序for(i=0;i<count;i++){bitNumber[i]=a[i]/10%10;}countSort(bitNumber,count,newA,c,a);for(i=0;i<count;i++){a[i]=newA[i];}//百位排序for(i=0;i<count;i++){bitNumber[i]=a[i]/100%10;}countSort(bitNumber,count,newA,c,a);for(i=0;i<count;i++){a[i]=newA[i];}//千位排序for(i=0;i<count;i++){bitNumber[i]=a[i]/1000%10;}countSort(bitNumber,count,newA,c,a);for(i=0;i<count;i++){a[i]=newA[i];}}voidmain(void){inta[]={23,1000,90,34,2,6,3,444,555,666,777,888,999,111,222};intcount=sizeof(a)/sizeof(int);radixSort(a,count);showArray(a,count);}

(3)、运行结果


(4)、算法分析

时间复杂度：O(n);