基数排序是许多人在按字母顺序对大量姓名进行排序时直观地使用的一个小方法。具体地，首先将姓名列表按照每个姓名的首字母进行排序，即将姓名分为26类。
直观地说，人们可能想要对数字的最高有效位进行排序。然而，基数排序是违反直觉的，首先对最低有效数字进行排序。在第一遍中，所有数字按最低有效位排序并组合成一个数组。然后在第二遍中，所有数字再次按第二个最不重要的数字进行排序，并组合成一个数组，依此类推。
算法：基数排序（列表，n）
移位=1
for 循环 = 1 到 keysize do
对于条目 = 1 到 n 做
桶编号 = (列表[条目].key / shift) mod 10
追加（存储桶[存储桶编号]，列表[条目]）
列表=组合桶()
平移 = 平移 * 10
一次查看每个键中最长键的每个数字（如果键是字母，则查看字母）。因此，如果最长的键有 m 个数字，并且有 n 个键，则基数排序的顺序为 O(mn) 。
但是，如果我们看这两个值，与键的数量相比，键的大小会相对较小。例如，如果我们有一个六位数字的密钥，则可能有一百万条不同的记录。
在这里我们看到密钥的大小并不重要，算法的线性复杂度为O(n)。
以下示例显示基数排序如何对七个 3 位数字进行运算。
| 输入 | 1st通过 | 2和通过 | 3rd通过 |
|---|---|---|---|
| 329 | 720 | 720 | 329 |
| 457 | 355 | 329 | 355 |
| 657 | 436 | 436 | 436 |
| 839 | 457 | 839 | 457 |
| 436 | 657 | 355 | 657 |
| 720 | 329 | 457 | 720 |
| 355 | 839 | 657 | 839 |
在上面的示例中，第一列是输入。其余列显示连续增加有效数字位置后的列表。基数排序的代码假设 n 元素A 的数组中 的每个元素都有一个 d 位，其中 1 位是最低位，而d为最高位置。
