基数排序算法

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

排序从每个元素的最低有效位开始。这些最低有效位都被视为单个元素并首先排序；然后是次低有效位。这个过程持续进行，直到输入元素的所有位都被排序。

注意 − 如果元素的位数不相等，则找到输入元素中位数的最大值，并在位数较少的元素前面添加前导零。这不会改变元素的值，但仍然使它们成为k位数。

基数排序算法

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

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

步骤2 − 获取每个元素的最低有效位。

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

步骤4 − 对下一个最低有效位重复步骤2，直到元素中的所有位都被排序。

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

伪代码

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

调用的countSort算法为：

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]

分析

假设输入元素中有k位，则基数排序算法的运行时间为Θ(k(n + b))。这里，n是输入列表中的元素个数，b是数字每一位可能取值的个数。

示例

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

步骤1

检查位数最多的元素，为3位。因此，我们为位数少于3位的数字添加前导零。我们得到的列表为：

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

步骤2

构建一个表来根据其索引存储值。由于给定的输入是十进制数，因此基于这些数字的可能值（即0-9）进行索引。

步骤3

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

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

步骤4

此步骤的输入顺序为上一步输出的顺序。现在，我们使用次低有效位进行排序。

获得的输出顺序为 001, 003, 026, 236, 042, 143, 056, 765, 482, 099。

步骤5

上一步后的输入列表重新排列为：

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

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

由于输入元素中没有其他位，因此此步骤中获得的输出被视为最终输出。

最终排序后的输出为：

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

实现

计数排序算法协助基数排序对多个d位数字进行迭代排序，循环次数为'd'。本教程中基数排序已使用四种编程语言实现：C、C++、Java、Python。

#include <stdio.h>
void countsort(int a[], int n, int pos){
   int output[n + 1];
   int max = (a[0] / pos) % 10;
   for (int i = 1; i < n; i++) {
      if (((a[i] / pos) % 10) > max)
         max = a[i];
   }
   int count[max + 1];
   for (int i = 0; i < max; ++i)
      count[i] = 0;
   for (int i = 0; i < n; i++)
      count[(a[i] / pos) % 10]++;
   for (int i = 1; i < 10; i++)
      count[i] += count[i - 1];
   for (int i = n - 1; i >= 0; i--) {
      output[count[(a[i] / pos) % 10] - 1] = a[i];
      count[(a[i] / pos) % 10]--;
   }
   for (int i = 0; i < n; i++)
      a[i] = output[i];
}
void radixsort(int a[], int n){
   int max = a[0];
   for (int i = 1; i < n; i++)
      if (a[i] > max)
         max = a[i];
   for (int pos = 1; max / pos > 0; pos *= 10)
      countsort(a, n, pos);
}
int main(){
   int a[] = {236, 15, 333, 27, 9, 108, 76, 498};
   int n = sizeof(a) / sizeof(a[0]);
   printf("Before sorting array elements are: ");
   for (int i = 0; i <n; ++i) {
      printf("%d ", a[i]);
   }
   radixsort(a, n);
   printf("\nAfter sorting array elements are: ");
   for (int i = 0; i < n; ++i) {
      printf("%d ", a[i]);
   }
   printf("\n");
}

Before sorting array elements are: 236 15 333 27 9 108 76 498 
After sorting array elements are: 9 15 27 76 108 236 333 498

#include <iostream>
using namespace std;
void countsort(int a[], int n, int pos){
   int output[n + 1];
   int max = (a[0] / pos) % 10;
   for (int i = 1; i < n; i++) {
      if (((a[i] / pos) % 10) > max)
         max = a[i];
   }
   int count[max + 1];
   for (int i = 0; i < max; ++i)
      count[i] = 0;
   for (int i = 0; i < n; i++)
      count[(a[i] / pos) % 10]++;
   for (int i = 1; i < 10; i++)
      count[i] += count[i - 1];
   for (int i = n - 1; i >= 0; i--) {
      output[count[(a[i] / pos) % 10] - 1] = a[i];
      count[(a[i] / pos) % 10]--;
   }
   for (int i = 0; i < n; i++)
      a[i] = output[i];
}
void radixsort(int a[], int n){
   int max = a[0];
   for (int i = 1; i < n; i++)
      if (a[i] > max)
         max = a[i];
   for (int pos = 1; max / pos > 0; pos *= 10)
      countsort(a, n, pos);
}
int main(){
   int a[] = {236, 15, 333, 27, 9, 108, 76, 498};
   int n = sizeof(a) / sizeof(a[0]);
   cout <<"Before sorting array elements are: ";
   for (int i = 0; i < n; ++i) {
      cout <<a[i] << " ";
   }
   radixsort(a, n);
   cout <<"\nAfter sorting array elements are: ";
   for (int i = 0; i < n; ++i) {
      cout << a[i] << " ";
   }
   cout << "\n";
}

Before sorting array elements are: 236 15 333 27 9 108 76 498 
After sorting array elements are: 9 15 27 76 108 236 333 498

import java.io.*;
public class Main {
   static void countsort(int a[], int n, int pos) {
      int output[] = new int[n + 1];
      int max = (a[0] / pos) % 10;
      for (int i = 1; i < n; i++) {
         if (((a[i] / pos) % 10) > max)
            max = a[i];
      }
      int count[] = new int[max + 1];
      for (int i = 0; i < max; ++i)
         count[i] = 0;
      for (int i = 0; i < n; i++)
         count[(a[i] / pos) % 10]++;
      for (int i = 1; i < 10; i++)
         count[i] += count[i - 1];
      for (int i = n - 1; i >= 0; i--) {
         output[count[(a[i] / pos) % 10] - 1] = a[i];
         count[(a[i] / pos) % 10]--;
      }
      for (int i = 0; i < n; i++)
         a[i] = output[i];
   }
   static void radixsort(int a[], int n) {
      int max = a[0];
      for (int i = 1; i < n; i++)
         if (a[i] > max)
            max = a[i];
      for (int pos = 1; max / pos > 0; pos *= 10)
         countsort(a, n, pos);
   }
   public static void main(String args[]) {
      int a[] = {236, 15, 333, 27, 9, 108, 76, 498};
      int n = a.length;
      System.out.println("Before sorting array elements are: ");
      for (int i = 0; i < n; ++i)
         System.out.print(a[i] + " ");
      radixsort(a, n);
      System.out.println("\nAfter sorting array elements are: ");
      for (int i = 0; i < n; ++i)
         System.out.print(a[i] + " ");
   }
}

Before sorting array elements are: 
236 15 333 27 9 108 76 498 
After sorting array elements are: 
9 15 27 76 108 236 333 498 

def countsort(a, pos):
   n = len(a)
   output = [0] * n
   count = [0] * 10
   for i in range(0, n):
      idx = a[i] // pos
      count[idx % 10] += 1
   for i in range(1, 10):
      count[i] += count[i - 1]
   i = n - 1
   while i >= 0:
      idx = a[i] // pos
      output[count[idx % 10] - 1] = a[i]
      count[idx % 10] -= 1
      i -= 1
   for i in range(0, n):
      a[i] = output[i]

def radixsort(a):
   maximum = max(a)
   pos = 1
   while maximum // pos > 0:
      countsort(a, pos)
      pos *= 10
      
a = [236, 15, 333, 27, 9, 108, 76, 498]
print("Before sorting array elements are: ")
print (a)
radixsort(a)
print("After sorting array elements are: ")
print (a)

Before sorting array elements are: 
[236, 15, 333, 27, 9, 108, 76, 498]
After sorting array elements are: 
[9, 15, 27, 76, 108, 236, 333, 498]