基数排序

基数排序得到递减序列的过程如下:

初始化:设置r个空队列(基数),Qr-1, Qr-2, ..., Q0

按照各个关键字位权重递增的次序,个、十、百对d个关键字位分别做”分配“和”收集“

分配:顺序扫描各个元素,若当前处理的关键字位=x,则将元素插入Qn队尾。

收集:把Qr-1, Qr-2, ..., Q0各个队列中的节点依次出队并链接。

需要r个辅助队列,空间复杂度为O(r)

一趟分配O(n),一趟收集O(r),总共d趟分配、收集,总的时间复杂度为O(d(n+r))

基数排序擅长解决的问题

  1. 数据元素的关键字可以方便的拆分为d组,且d较小。
  2. 每组关键字的取值范围不大,即r较小。
  3. 数据元素个数较大。
上一篇:摧毁图状树 [20220210 模拟赛] 贪心/调和级数/线段树


下一篇:mysql45讲(2)