首页 > 代码库 > 计数排序算法
计数排序算法
基本思想:
统计数组data,小于data[i]的个数为N,则把data[i]放在第N+1个位置上面。
实用范围:
所有数都在[0,max]范围内,max为数组的最大值,适用于max不是很大的情况。
对于数据2 5 3 0 2 3 0 3程序执行的过程如下图所示:
C++代码:
#include <iostream> using namespace std; namespace mysort {//找出数组中的最大值 int Max(int * data, int len) { int ret = -1; for (int i = 0; i < len; i++) if (data[i]>ret) ret = data[i]; return ret; } void sort(int *data, int len) { int max = Max(data, len); int *c = new int[max+1]; int *ret = new int[len]; memset((void*)c, 0, sizeof(int)* (max + 1)); for (int i = 0; i < len; ++i) c[data[i]]++;//统计每个数出现的次数 for (int i = 0; i < max; i++) c[i + 1] += c[i];//统计小于某个数出现的次数 for (int i = len - 1; i >= 0; i--) { ret[ c[ data[i] ] - 1 ] = data[i]; --c[data[i]]; } memcpy((void*)data, (void*)ret, sizeof(int)*len); } }; int main() { //计数排序的前提是,所有数都在[0,max]范围内,适用于数组最大值不是很大的情况。 int a[] = { 0, 4, 3, 1, 2, 3, 4, 5, 6, 4, 3, 2 }; mysort::sort(a, 12); return 0; }
总结:计数排序和通常的交换排不同,它直接将待排序的数放在了排序后正确的位置。算法虽然有O(N)的时间和空间复杂度,但它的使用范围有一定的局限性。算法思路和用位向量排序(《编程珠玑》第一章)有相似之处。
Key Word:不同问题,不同的分析。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。