甲乙小朋友的房子

甲乙小朋友很笨,但甲乙小朋友不会放弃

0%

计数排序、基数排序、桶排序

非比较排序

插入排序、归并排序、堆排序、快速排序这四种排序算法,他们的运行时间上界不会超过O(nlgn)。这些算法都有一个有趣的性质:在排序的最终结果中,各元素的次序依赖于它们之间的比较。我们把这类排序算法称为比较排序。

可以证明,基于比较的排序算法在最坏情况下的时间下界是Ω(nlgn)。堆排序和归并排序的运行时间上界为O(nlgn),因此这两种排序算法都是渐进最优的比较排序算法。

非基于比较的排序,如计数排序,桶排序,和在此基础上的基数排序,则可以突破O(NlogN)时间下限,达到线性时间复杂度\[O(n)\]。但要注意的是,非基于比较的排序算法的使用都是有条件限制的,例如元素的大小限制,相反,基于比较的排序则没有这种限制(在一定范围内)。但并非因为有条件限制就会使非基于比较的排序算法变得无用,对于特定场合有着特殊的性质数据,非基于比较的排序算法则能够非常巧妙地解决。

基数排序:O(dn) (d次调用桶排序),空间复杂度 O(k)

桶排序:O(n)时间复杂度,O(n)空间复杂度

计数排序:O(n)时间复杂度,O(k)空间复杂度,每一个元素都是整数,并且位于0到k - 1之间

计数排序

计数排序假设n个输入元素中的每一个都是在0到k区间内的一个整数,其中k为某个整数。当k=O(n)时,排序的运行时间为Θ(n)。

计数排序的思想是,对每一个输入元素,计算小于它的元素个数,如果有10个元素小于它,那么它就应该放在11的位置上,如果有17个元素小于它,它就应该放在18的位置上。当有几个元素相同时,这一方案要略做修改,因为不能把它们放在同一个输出位置上。下图展示了实际的运行过程。

img

计数排序

构造辅助数组C,C的长度为k。第一次遍历A后,得到[0,k)区间上每个数出现的次数,将这些次数写入C,得到图(a)的结果。然后把C中每个元素变成前面所有元素的累加和,得到图(b)的结果。接下来,再次从后向前遍历数组A,根据取出的元素查找C中对应下标的值,再把这个值作为下标找到B中的位置,即是该元素排序后的位置。例如,图中A的最后一个元素是3,找到C[3]是7,再令B[7]=3即可,然后顺便把C[3]减一,这是防止相同的数被放到同一个位置。

计数排序的时间代价可以这样计算,第一次遍历A并计算C所花时间是Θ(n),C累加所花时间是Θ(k),再次遍历A并给B赋值所花时间是Θ(n),因此,总时间为Θ(k + n)。在实际中,当k=O(n)时,我们一般会采用计数排序,这时的运行时间为Θ(n)。

基数排序

对于一组数据,我们可以按照每一位对它们进行排序。比如,考虑下面一组十进制数 329 457 839 355

先按最后一位从小到大排序,得到 355 457 329 839

再按中间一位从小到大排序,得到 329 839 355 457

最后按第一位从小到大排序,得到 329 355 457 839

其中,对任何一位的排序算法必须是稳定的,即相同数字不能改变它们的前后顺序。

基数排序算法的运行时间很容易计算,对于n个k进制d位数,假如每一位的排序使用计数排序算法,则该位排序用时为Θ(n + k),总共d位数,总排序用时就是Θ(d(n + k))。当d为常数且k=O(n)时,总排序时间为Θ(n)。

桶排序

桶排序假设输入是由一个随机过程产生,该过程将元素均匀、独立地分布在[0,1)区间上。

我们将[0,1)区间划分为n个相同大小的子区间,称为桶。然后将输入数据分别放到各个桶中。如果数据分布得很均匀,每个桶中的数据就不会太多,都会维持在常数量级。我们先对每个桶中的元素排序,然后把所有桶中的元素顺序列出来即可。下图为n=10的一个案例。

img

桶排序.png

创建一个长度也为10的数组,将A中的元素按照大小找到B中合适的位置,插入链表。之后,分别对B中每个链表中的元素执行插入排序。最后将B中的所有元素依次取出即可。

现在分析桶排序的时间代价。将A中元素放入B用时Θ(n),B中每个链表执行插入排序的用时,可以证明是O(2 - 1/n),于是总用时就是Θ(n) + n * O(2 - 1/n) = Θ(n)。具体证明过程比较难理解,这里我想给出一个容易理解的解释,虽然不一定对,但还是可以帮助理解为什么总用时是Θ(n)。n个数放入n个桶,平均下来每个桶只有一个数,在实际中,可能有的多有的少,但都不会差得太离谱。因此我们可以认为每个桶中只有常数个数,那么对常数个数执行插入排序所用的时间当然也就是O(1)了。于是n个桶总用时就是O(n),加上前面的Θ(n),桶排序总用时就是Θ(n)了。