一天一算法 – 桶排序

介绍

桶排序可以说得上是最简单的排序算法了,但是它的使用范围非常狭窄,不过不可否认的是在其适用范围内,它的性能要比快速排序还要快上很多倍。

没错,桶排序也是一种非比较型排序算法,这也正是它能够超越快速排序的原因。

桶排序主要有以下缺陷:

  1. 参与排序的数组存放的必须是整数。
  2. 数组中的最大数和最小数保持在一个合理的间距内。
  3. 需要额外的内存空间。

下面将通过一个例子讲解桶排序的核心思想:

假如说我们需要对全国高考语文成绩进行排序,由于总分只有 150 分,而且所有的值都在 [0, 150] 之间,所以我们可以申请一个大小为 151 的辅助数组。

首先我们将数组的值都置为 0。然后我们以各考生的成绩为下标递增辅助数组的值。比如说一个考生成绩为 90,那么我们就让 countArray[90]++,这样一直运算下去,直到所有的考生成绩都被遍历完,我们就可以统计出来每个分数有多少考生,然后再将辅助数组中的值复制回原数组,整个数组自然而然就有序了!


实现

大概了解了桶排序的思想,下面就来实现一下,假说某年参加高考的学生共有 500 万人,我们对其语文成绩进行排序。

下面是排序代码:

下面是测试代码:

以上代码在我电脑上的运行时间在 23ms 左右,可见,桶排序排序 500万数据的速度是如此之快,而我用快速排序对同一个数组进行排序,花了 320 ms 左右。

所以,如果在合适的时机选择计数排序,将节省很多时间。


改进

看了以上代码也许你发现了,上述代码如果排序一个数值在 [10000, 10200] 范围内的数组的话,将申请大量的内存,为了节省内存,我们不得不改进这个算法,让其适应指定范围内排序。

很简单的,我们可以在方法中设置一个 low 和 max 参数,就可以灵活自如了。


总结

最近一直在学习排序算法,发现比较型算法虽然速度比较慢一些(比较型算法的下限是 O(NlogN)),但是适用范围很广。非比较型算法虽然使用范围很有限,但是其速度非常之快。所以在选择排序算法时,根据程序的数值类型以及范围,首先要考虑是否能够使用非比较型算法,如果不可以再选用比较型算法,比如快速排序。

我已经将我写过的排序算法的代码全部放到了 我的 Github, 如果有兴趣可以前去阅览一下。

《一天一算法 – 桶排序》有2个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注