基数排序

基数排序是一种排序算法，当存在常数 'd' 使得所有关键字都是 d 位数时，它很有用。要执行基数排序，对于 p = 1 到 'd'，使用任何线性时间稳定排序，根据从右侧起的第 P 位数字对数字进行排序。

基数排序的代码很简单。 以下过程假定 n 元素数组 A 中的每个元素都有 d 位数字，其中数字 1 是最低有效位数字，数字 d 是最高有效位数字。

以下是用于对 A [1.n] 进行排序的算法，其中每个数字的长度为 d 位。

RADIX-SORT (array A, int n, int d) 
 1 for i ← 1 to d 
 2 do stably sort A to sort array A on digit i

示例： 第一列是输入。 剩余的列显示了在对越来越重要的数字位置进行连续排序后的列表。 垂直箭头指示了对数字位置进行排序以生成每个列表的位置。