设计与分析 - 基数排序

基数排序是一种逐步排序算法，从输入元素的最低有效数字开始排序。与计数排序和桶排序一样，基数排序也假设输入元素都是 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]