基數排序演算法

基數排序是一種逐步排序演算法，它從輸入元素的最低有效位開始排序。與計數排序和桶排序一樣，基數排序也假設輸入元素有一些特性，即它們都是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]