首页 > 代码库 > 计数排序
计数排序
前言
一般的排序都是需要进行关键字的比较的。有没有不需要比较的的呢?有的,计数排序就是其中一种。
计数排序
假设输入序列都是0到k之间的整数,则可使用计数排序。具体操作是这样的:创建一个同类型同等大小的临时数组temp,用于备份输入序列。创建一个整型大小为k的数组count,用于统计序列中各元素出现的次数。接下来只需把备份序列从大到小放回原数组即可。一个示例图:
仔细看图,很容易理解的。并且可以看出计数排序是稳定的,下面给出它的示例代码;
代码
#include<stdio.h> #include<stdlib.h> #include<memory.h> #include<time.h> void print(int *a, int n) { for (int i = 0; i < n; i++) printf("%4d",a[i]); printf("\n"); } int get_max(int *a, int n) { int max = a[0]; for (int i = 1; i < n; i++) { if (a[i]>max) max = a[i]; } //加一后返回 return max+1; } /* n是序列个数 max是序列中元素最大值[0,max) */ void CountSort(int array[], int n, int max) { int i; int *temp = (int*)malloc(n*sizeof(int)); int *count = (int*)malloc(max*sizeof(int)); //初始化临时数组 memcpy(temp, array, n*sizeof(int)); //初始化计数数组 memset(count, 0, max*sizeof(int)); //计数 for (i = 0; i < n; i++) count[array[i]]++; //计算位置 for (i = 1; i < max; i++) count[i] += count[i - 1]; //回放序列,方向:从后往前 for (i = n - 1; i >= 0; i--) array[--count[temp[i]]] = temp[i]; //释放空间 delete[]temp; delete[]count; } int main() { printf("***计数排序***by David***\n"); srand((unsigned)time(0)); int a[] = {2,3,1,5,1,6,4,9}; int n = sizeof(a) / sizeof(int); printf("原序列\n"); print(a, n); printf("计数排序\n"); CountSort(a, n, get_max(a, n)); print(a, n); system("pause"); return 0; }
运行
算法分析
整个排序过程我们都没有进行关键字比较,不得不说,这种做法很新颖。但计数排序也是有适用范围的:它是在序列元素都是位于[0,k)之间的情况下的一种有效排序算法。排序中我们用到了一个临时数组和一个计数数组,故空间复杂度是O(n+k)。时间主要消耗在计数和回放,故时间复杂度是O(n+k)。所以当元素普遍比较小的时候,即k较小时:k=O(n),时间复杂度是O(n),这是线性的。而当k较大时,不仅时间上不划算,空间上也不划算。
转载请注明出处,本文地址:http://blog.csdn.net/zhangxiangdavaid/article/details/37605511
若有所帮助,顶一个哦!
专栏目录:数据结构与算法目录
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。