跳转至

基数排序

基数排序是将待排序码拆分成多个部分分别来比较。

按照排序码的先后顺序,分为两种:

  1. 高位优先(MSD) 先对高位排序,分成若干子序列,对每个子序列根据较低位排序,是一个分、分、……、分、收的过程。
  2. 低位优先(LSD) 从低位开始,对于排好的序列用次低位排序,(每次排序的都是全体元素)是一个分、收、分、收、……、分、收的过程。

低位优先速度较快,便于处理,更常用。

基数排序对关键码值进行 O(\log_r n)次运算,因此处理 n 个不同的关键码时,基数排序的时间代价为 O(n \log n)

参考

http://atool.org/sort.phpATool 的排序演示动画
https://www.geeksforgeeks.org/counting-sort/


评论