Data Structures Algorithms 简明教程
Radix Sort Algorithm
基数排序是一种逐步排序算法，它从输入元素的最低有效数字开始进行排序。像计数排序和桶排序一样，基数排序也对输入元素进行了一些假设，即它们都是 k 位数字。
排序从每个元素的最低有效数字开始。这些最低有效数字都被考虑为单独的元素并首先排序；其次是最次要有效数字。此过程将持续到输入元素的所有数字都排序完成为止。
Note - 如果元素没有相同数量的数字，则找到输入元素的最大位数，并在位数较少的元素中添加前导零。这不会改变元素的值，但仍会使它们成为 k 位数字。
Radix Sort Algorithm
基数排序算法在每个阶段进行排序时都会利用计数排序算法。详细步骤如下：
步骤 1 - 检查所有输入元素是否具有相同数量的数字。如果不是，请检查列表中具有最大位数的数字，并在位数较少的数字中添加前导零。
步骤 2 - 取每个元素的最低有效数字。
步骤 3 - 使用计数排序逻辑对这些数字进行排序，并根据获得的输出更改元素的顺序。例如，如果输入元素是小数，则每个数字可以取的值为 0-9，因此请根据这些值对数字进行索引。
步骤 4 - 对下一个最低有效数字重复步骤 2，直到元素中的所有数字都排序完成。
步骤 5 - 第 k 次循环后获得的最终元素列表是排序后的输出。
Pseudocode
Algorithm: RadixSort(a[], n):
// Find the maximum element of the list
max = a[0]
for (i=1 to n-1):
if (a[i]>max):
max=a[i]
// applying counting sort for each digit in each number of
//the input list
For (pos=1 to max/pos>0):
countSort(a, n, pos)
pos=pos*10调用的计数排序算法将是 −
Algorithm: countSort(a, n, pos)
Initialize count[0…9] with zeroes
for i = 0 to n:
count[(a[i]/pos) % 10]++
for i = 1 to 10:
count[i] = count[i] + count[i-1]
for i = n-1 to 0:
output[count[(a[i]/pos) % 10]-1] = a[i]
i--
for i to n:
a[i] = output[i]Example
对于给定的未排序元素列表，236、143、26、42、1、99、765、482、3、56，我们需要执行基数排序并获取排序后的输出列表 −
Step 1
检查位数最多的元素，为 3。因此，我们向没有 3 位数字的数字添加前导零。我们达到的列表将是 −
236, 143, 026, 042, 001, 099, 765, 482, 003, 056Step 2
构造一个表以根据索引存储值。由于给定的输入是小数，因此索引是根据这些数字的可能值（即 0-9）完成的。
Step 3
根据所有数字的最小有效位数，将数字放在其各自的索引上。
此步骤后排序的元素将为 001、042、482、143、003、765、236、026、056、099。
Step 4
此步骤的输入顺序将是前一步骤中输出的顺序。现在，我们使用第二最小有效位数进行排序。
实现的输出顺序为 001、003、026、236、042、143、056、765、482、099。
Step 5
前一步骤后的输入列表被重新排列为 −
001, 003, 026, 236, 042, 143, 056, 765, 482, 099现在，我们需要对输入元素的最后一位数字进行排序。
由于输入元素中没有更多的数字，因此此步骤中实现的输出被认为是最终输出。
最终排列的输出为 −
1, 3, 26, 42, 56, 99, 143, 236, 482, 765