线性时间排序--计数和基数排序
1、计数排序
为灵石等地区用户提供了全套网页设计制作服务,及灵石网站建设行业解决方案。主营业务为成都网站设计、成都网站制作、灵石网站设计,以传统方式定制建设网站,并提供域名空间备案等一条龙服务,秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求,就会得到认可,从而选择与我们长期合作。这样,我们也可以走得更远!
(1)、算法思想
是一组在特定范围内的整数,在线性时间内排序,比nlog(n)更快的排序算法;
较小范围内是比较好的排序算法,如果很大是很差的排序算法;
可以解决重复元素的出现的排序算法;
(2)、代码实现
#includevoid countSort(int *a, int count); void showArray(int *a, int count); void showArray(int *a, int count){ int i; for(i = 0; i < count; i++){ printf("%d ", a[i]); } printf("\n"); } void countSort(int *a, int count){ int b[10] = {0}; int *c; int i; 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); } void main(void){ int a[] = {2, 4, 7, 2, 1, 0, 9}; int count = sizeof(a)/sizeof(int); countSort(a, count); showArray(a, count); }
(3)、结果截图
(4)、算法分析:
计数排序优点:稳定性(一个稳定性算法保证了相等元素的顺序);
时间复杂度:O(n);
2、基数排序
(1)、算法思想
i、从最后一位(低位-->高位)开始排序,并且的是稳定的排序算法(辅助算法:计数排序),整体思想:按位排序;
ii、在进行基数排序时,从个位--->十位--->百位......每取一位时,分别进行计数排序,传的参数:位、要排序的总数、新的结果、辅助空间(开辟10个元素的空间)、原先数组;利用位和辅助空间,将原先数组的值放入新的结果空间中即可;(位的顺序与原先结果的顺序保持一致)!!!
iii、基数排序只要知道最大数是几位,进行几次排序即可;
(2)、代码实现
#include#include void radixSort(int *a, int count); void countSort(int *bitNumber, int count, int *newA, int *c, int *a); void showArray(int *a, int count); void showArray(int *a, int count){ int i; for(i = 0; i < count; i++){ printf("%d ", a[i]); } printf("\n"); } void countSort(int *bitNumber, int count, int *newA, int *c, int *a){ int i; //从个位-->十位-->百位,每一次调用这个函数,辅助空间都必须初始化为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]]--; } } void radixSort(int *a, int count){ int *bitNumber; int *newA; int c[10] = {0}; int i; //个位进行排序 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]; } } void main(void){ int a[] = {23, 1000, 90, 34, 2, 6, 3, 444, 555, 666, 777, 888, 999, 111, 222}; int count = sizeof(a)/sizeof(int); radixSort(a, count); showArray(a, count); }
(3)、运行结果
(4)、算法分析
时间复杂度:O(n);
文章名称:线性时间排序--计数和基数排序
转载来源:http://scyanting.com/article/pjhphi.html