基数排序算法

基数排序是一种排序算法, 当存在常数“ d”（所有键均为d位数字）时很有用。要执行“基数排序”, 对于p = 1朝“ d”, 使用任何线性时间稳定排序从右开始对数字进行排序。

基数排序代码很简单。以下过程假定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

示例：第一列是输入。剩余的列显示了在连续递增的有效数字位置后的列表。垂直箭头指示排序的数字位置, 以产生前一个列表的每个列表。

576     49[4]     9[5]4     [1]76     176
494     19[4]     5[7]6     [1]94     194
194     95[4]     1[7]6     [2]78     278
296   → 57[6]  →  2[7]8   → [2]96   → 296
278     29[6]     4[9]4     [4]94     494
176     17[6]     1[9]4     [5]76     576
954     27[8]     2[9]6     [9]54     954