sorting - 有人可以向我解释基数排序吗？

Question

我正在尝试在 javascript 中实现基数排序。但是，我不知道如何进行基数排序！我有这个伪代码（来自算法简介）：

RADIX-SORT(A, d)
    for i = 1 to d
        use a stable sort to sort array A on digit i

但是，当它说 时A on digit i，那是什么意思？

Answer 1

在基数排序中，元素根据第 i 个数字进行排序。它通过查看数字 1 开始对数组 A 进行排序，然后是 2，... 直到数字 d。

例如：A = {423、241、732}

迭代 1 (i=1): A = {24 1 ,73 2 ,42 3 }

迭代 2 (i=2)：A = {4 2 3,7 3 2,2 4 1}

迭代 3 (i=3): A = { 2 41, 4 23, 7 32} --排序**

这需要线性时间来对包含 n 个元素的数组进行排序（取决于内部使用的稳定排序）。这在 O(n+d) 时间内进行排序，其中 d 是元素中的位数。

我们可以使用任何稳定的排序（计数排序或任何其他）对元素进行排序。