基数排序是一种排序算法, 当存在常数“ 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