线性排序:桶排序 计数排序 基数排序

  • A+
所属分类:算法与数据结构

线性排序:桶排序 计数排序 基数排序

桶排序(Bucket Sort)

将数据装在几个桶中,每个桶单独排序,最后将数据按顺序依次取出,即为有序的了。

复杂度

分成m个桶,每个桶中n/m个数据,使用快排,那么总的时间复杂度为O(m* n/m * log(n/m)) = O(n * log(n/m))。当桶的数目m接近n时,log(n/m)很小,则时间复杂度为O(n)。

空间复杂度:至少为O(n)

稳定性:由每个桶中的排序算法决定。

条件

  1. 桶与桶之间有天然的大小顺序。这样在每个桶排好序后,就不需要再排序了。
  2. 数据在各个桶中分布比较均匀。最坏的情况下,数据都分到一个桶中,那么时间复杂度退到O(nlog(n))。

应用

外部排序:数据太多,不能全部加载到内存中。

先遍历一次,找到数据的范围。设置桶,即分别创建几个文件,将数据保存在这几个文件中。将每个文件分别加载到内存中排序。最后将这几个文件合并为一个大文件。

计数排序(Counting Sort)

可以看作桶排序的一种特例。适用于非负数的排序,且数据的最大值不能比数据的长度大很多。

将数据的值作为另一个数组的下标,value为此下标代表的值出现的次数。然后从0开始累加,表示此下标代表的值是从小到大排序后第几个数字。

代码

条件

非负,数据范围不大,数据的最大值不能为数据量大很多

复杂度

时间复杂度:O(n+k)

空间复杂度:O(n+k) k为数据范围

稳定性:稳定的。

应用

如果有负数,可以整体加一个数,使其为正。有小数,则可乘倍数,成整数。

基数排序(Radix Sort)

即每一位分别进行排序,要求每一位的排序算法是稳定的,不然在其他位排序后,此位的排序就无用了。

复杂度

每一位用计数排序则O(n),共k位,则O(k*n),若k比较小,则时间复杂度位O(n)。

LTXU

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: