Data Structures Algorithms 简明教程

Radix Sort Algorithm

基数排序是一种逐步排序算法，它从输入元素的最低有效数字开始进行排序。像计数排序和桶排序一样，基数排序也对输入元素进行了一些假设，即它们都是 k 位数字。

Radix sort is a step-wise sorting algorithm that starts the sorting from the least significant digit of the input elements. Like Counting Sort and Bucket Sort, Radix sort also assumes something about the input elements, that they are all k-digit numbers.

排序从每个元素的最低有效数字开始。这些最低有效数字都被考虑为单独的元素并首先排序；其次是最次要有效数字。此过程将持续到输入元素的所有数字都排序完成为止。

The sorting starts with the least significant digit of each element. These least significant digits are all considered individual elements and sorted first; followed by the second least significant digits. This process is continued until all the digits of the input elements are sorted.

Note - 如果元素没有相同数量的数字，则找到输入元素的最大位数，并在位数较少的元素中添加前导零。这不会改变元素的值，但仍会使它们成为 k 位数字。

Note − If the elements do not have same number of digits, find the maximum number of digits in an input element and add leading zeroes to the elements having less digits. It does not change the values of the elements but still makes them k-digit numbers.

Radix Sort Algorithm

基数排序算法在每个阶段进行排序时都会利用计数排序算法。详细步骤如下：

The radix sort algorithm makes use of the counting sort algorithm while sorting in every phase. The detailed steps are as follows −

步骤 1 - 检查所有输入元素是否具有相同数量的数字。如果不是，请检查列表中具有最大位数的数字，并在位数较少的数字中添加前导零。

*Step 1 *− Check whether all the input elements have same number of digits. If not, check for numbers that have maximum number of digits in the list and add leading zeroes to the ones that do not.

步骤 2 - 取每个元素的最低有效数字。

*Step 2 *− Take the least significant digit of each element.

步骤 3 - 使用计数排序逻辑对这些数字进行排序，并根据获得的输出更改元素的顺序。例如，如果输入元素是小数，则每个数字可以取的值为 0-9，因此请根据这些值对数字进行索引。

*Step 3 *− Sort these digits using counting sort logic and change the order of elements based on the output achieved. For example, if the input elements are decimal numbers, the possible values each digit can take would be 0-9, so index the digits based on these values.

步骤 4 - 对下一个最低有效数字重复步骤 2，直到元素中的所有数字都排序完成。

*Step 4 *− Repeat the Step 2 for the next least significant digits until all the digits in the elements are sorted.

步骤 5 - 第 k 次循环后获得的最终元素列表是排序后的输出。

*Step 5 *− The final list of elements achieved after kth loop is the sorted output.

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

调用的计数排序算法将是 −

The countSort algorithm called would be −

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]

Analysis

由于输入元素中有 k 位数字，因此基数排序算法所用的运行时间将为 Θ(k(n + b) 。这里，n 是输入列表中的元素数，而 b 是数字的每一位可以取的可能值的数量。

Given that there are k-digits in the input elements, the running time taken by the radix sort algorithm would be Θ(k(n + b). Here, n is the number of elements in the input list while b is the number of possible values each digit of a number can take.

Example

对于给定的未排序元素列表，236、143、26、42、1、99、765、482、3、56，我们需要执行基数排序并获取排序后的输出列表 −

For the given unsorted list of elements, 236, 143, 26, 42, 1, 99, 765, 482, 3, 56, we need to perform the radix sort and obtain the sorted output list −

Step 1

检查位数最多的元素，为 3。因此，我们向没有 3 位数字的数字添加前导零。我们达到的列表将是 −

Check for elements with maximum number of digits, which is 3. So we add leading zeroes to the numbers that do not have 3 digits. The list we achieved would be −

236, 143, 026, 042, 001, 099, 765, 482, 003, 056

Step 2

构造一个表以根据索引存储值。由于给定的输入是小数，因此索引是根据这些数字的可能值（即 0-9）完成的。

Construct a table to store the values based on their indexing. Since the inputs given are decimal numbers, the indexing is done based on the possible values of these digits, i.e., 0-9.

Step 3

根据所有数字的最小有效位数，将数字放在其各自的索引上。

Based on the least significant digit of all the numbers, place the numbers on their respective indices.

此步骤后排序的元素将为 001、042、482、143、003、765、236、026、056、099。

The elements sorted after this step would be 001, 042, 482, 143, 003, 765, 236, 026, 056, 099.

Step 4

此步骤的输入顺序将是前一步骤中输出的顺序。现在，我们使用第二最小有效位数进行排序。

The order of input for this step would be the order of the output in the previous step. Now, we perform sorting using the second least significant digit.

实现的输出顺序为 001、003、026、236、042、143、056、765、482、099。

The order of the output achieved is 001, 003, 026, 236, 042, 143, 056, 765, 482, 099.

Step 5

前一步骤后的输入列表被重新排列为 −

The input list after the previous step is rearranged as −

001, 003, 026, 236, 042, 143, 056, 765, 482, 099

现在，我们需要对输入元素的最后一位数字进行排序。

Now, we need to sort the last digits of the input elements.

由于输入元素中没有更多的数字，因此此步骤中实现的输出被认为是最终输出。

Since there are no further digits in the input elements, the output achieved in this step is considered as the final output.

最终排列的输出为 −

The final sorted output is −

1, 3, 26, 42, 56, 99, 143, 236, 482, 765

Implementation

计数排序算法帮助基数排序对多位数字 d 依次进行排序，持续进行 ‘d’ 次循环。本教程中用四种编程语言实现了基数排序：C、C++、Java、Python。

The counting sort algorithm assists the radix sort to perform sorting on multiple d-digit numbers iteratively for ‘d’ loops. Radix sort is implemented in four programming languages in this tutorial: C, C++, Java, Python.