今天无聊就打算把所有的排序算法都看一遍。。。

  1. 计数排序的时间复杂度是O(n),在算法导论中,用决策树模型中论证了,比较排序的情况为nlogn的复杂度。而计数排序的时间复杂度小于他的原因就是它不需要进行比较。
  2. 计数排序的原理就是根据原数组(A)里面最大的元素来一个与其一样大的数组(B),新开的数组(B)的第 i 个元素的值就是 i 在原数组(A)里面出现的次数.这样就可以根据新开的数组(B)来确定原数组(A)的排序。

我们先来看看排序部分的实现:(len是数组的长度)

void countSort(int *arrayL, int len) {
int findMax = 0;
for (int i = 0; i != len; i++)
if (findMax < arrayL[i])
findMax = arrayL[i];
findMax += 1; //元素应该是从 1 开始,而数组下标是从 0 开始,所以加 1
int *sortArray = new int[findMax]; //开始设定每个元素出现的次数都为 0
for (int i = 0; i != findMax; i++)
sortArray[i] = 0; //当对应的元素出现时,个数加 1
for (int i = 0; i != len; i++)
++sortArray[arrayL[i]]; //排序
int count = 0;
for (int i = 0; i != len; i++) {
for (int j = count; j != findMax; j++) {
count++; // sortArray 中在 count 前面的元素已经遍历过了
if (sortArray[j] != 0) {
//这里 for 循环是当出现元素个数不为 1 的情况时
for (int k = 0; k != sortArray[j]; k++) {
arrayL[i++] = j; //将元素的值赋到原数组
}
i--; //for 循环里面还会自增
break;
}
}
}
}

 这部分的代码应该不难理解,因为基本都已经在代码注释说明了。这里原理就是,新开的数组的下标就是原数组的元素值。这样的话,当新开的数组某下标对应的值不为 0 时,代表该下标值在原数组出现过,而我们知道下标是有序的,那么就可以在遍历新建数组的时候有序地将有在原数组出现过的值赋给原数组。这样原数组就变得有序了。

但根据这个算法的实现我们可以看出,它并不适合当数组的元素值很大的时候。因为这样的话新开的数组空间很大,当输入的元素是 n 个 0 到 k 之间的整数时,它的运行时间是 Θ(n + k),那么当K很大时,新开数组太大,既浪费空间,时间上也会有很大开销,因为虽然看上去是Θ(n + k),但当k很大时时间还是很长的。所以当需要排序的数组的元素值均在0~100之间时会比较适合。特别是当有很多元素重复的时候。另外,对于浮点数,字符串的排序他也无能为力。

其实,还有一个地方用这个算法的话会比较好,那就是在基数排序中比较每个位数的时候,因为每位数都是在0~9之间,用这个算法就很perfect了。。。

最新文章

  1. java并行计算Fork和Join的使用
  2. Winform MDI窗体容器 权限 简单通讯
  3. Firemonkey TComboBox 下拉菜单字型修改方法 (D10)
  4. Java遇见HTML——JSP篇之商品浏览记录的实现
  5. NYOJ214
  6. BPEL_Oracle BPEL新一代工作流介绍(概念)
  7. APACHE 403 FORBIDDEN错误的解决办法之一
  8. java main()静态方法
  9. ROS学习笔记(九)——ROSSERVICE
  10. 【HDOJ】2526 浪漫手机
  11. Sublime Text 高级正则查换替换功能
  12. SVN和Git的一些用法总结(转)
  13. android开发注意点
  14. Java学习笔记——Linux下安装配置MySQL
  15. Redis管理之持久化
  16. 如何为ASP.NET Core设置客户端IP白名单验证
  17. pytest框架之fixture详细使用
  18. java 学习------helloword 程序测试
  19. POJ 3903 Stock Exchange 【最长上升子序列】模板题
  20. dede 栏目及子栏目

热门文章

  1. javascript中检测一个变量的类型
  2. CSS定义input disabled样式
  3. P1349 广义斐波那契数列
  4. HDFS文件操作命令手册
  5. 转:Lucene之计算相似度模型VSM(Vector Space Model) : tf-idf与交叉熵关系,cos余弦相似度
  6. 【刷题】BZOJ 2038 [2009国家集训队]小Z的袜子(hose)
  7. [SCOI2013]摩托车交易 kruskal重构树(最大生成树) 倍增
  8. 51NOD 1353:树——题解
  9. PE格式示意图
  10. [zhuan]动态链接库中的.symtab和.dynsym