算法系列:计数排序

计数排序可能是最简单的一种排序,它可以被用来对一个列表进行排序,并且是基数排序的一个关键部分。这两者都是被Harold Seward发明的,这篇文章我将解释计数排序并且用C写出来。

  • 计数排序

计数排序非常基础,他的主要目的是对整数排序并且会比普通的排序算法性能更好。例如,输入{1, 3, 5, 2, 1, 4}给计数排序,会输出{1, 1, 2, 3, 4, 5}。这个算法由以下步骤组成:

  1. 初始化一个计数数组,大小是输入数组中的最大的数。
  2. 遍历输入数组,遇到一个数就在计数数组对应的位置上加一。例如:遇到5,就将计数数组第五个位置的数加一。
  3. 把计数数组直接覆盖到输出数组(节约空间)。
  • 例子

输入{3, 4, 3, 2, 1},最大是4,数组长度是5。

建立计数数组{0, 0, 0, 0}。

遍历输入数组:

{3, 4, 3, 2, 1} -> {0, 0, 1, 0}
{3, 4, 3, 2, 1} -> {0, 0, 1, 1}
{3, 4, 3, 2, 1} -> {0, 0, 2, 1}
{3, 4, 3, 2, 1} -> {0, 1, 2, 1}
{3, 4, 3, 2, 1} -> {1, 1, 2, 1}

计数数组现在是{1, 1, 2, 1},我们现在把它写回到输入数组里:

{0, 1, 2, 1} -> {1, 4, 3, 2, 1}
{o, o, 2, 1} -> {1, 2, 3, 2, 1}
{o, o, 1, 1} -> {1, 2, 3, 2, 1}
{o, o, o, 1} -> {1, 2, 3, 3, 1}
{o, o, o, o} -> {1, 2, 3, 3, 4}

这样就排好序了。

  • 时间:O(n + k),n是输入数组长度,k是最大的数的大小。
  • 空间:O(n + k),n是输入数组长度,k是最大的数的大小。
  • 代码

插播一句:如果你编程有困难,无妨看看我的教程

  • 总结

不幸的是,这个算法的简洁性同时也是它的弱点。很多程序员不需要对整数排序,至少他们觉得他们不需要。其实通常非整数都可以被规约为整数,然后再用计数排序或者基数排序(基数排序就是多加了一层,这样会快一些)。谷歌一下可以有不少结果,比如这篇文章

4 收藏 8 评论

关于作者:大飞

(新浪微博:@大飞小飞飞飞飞) 个人主页 · 我的文章 · 1

相关文章

可能感兴趣的话题



直接登录
最新评论
  • dlitchi   2014/08/03

    遇到0怎么办?遇到负数怎么办?

    • link   2014/08/04

      计数排序有个假设的前提->每个输入元素都是基于0到k之间的整数

  • xiexiangh69   2014/08/04

    给的例子代码好像有两个bug,

  • 丁亚光   2014/08/09

    =.= 这不就是桶排序么....应用场景太少了

  • 其实也可以通过偏移来解决数组中存在负数的情况,这样的话,最终计数的数组大小应该是数组元素的范围。如果需要对字符串排序,可以通过字符串哈希算法,转化为整数再进行统计,当然,和布隆一样,应用字符串哈希算法,得到得到结果总是不一定正确的。

  • 墨菲   04/15

    计数、基数、桶排序之间的区别一直傻傻分不清楚,哈哈。

跳到底部
返回顶部