// C++ implementation of Radix Sort #include  using namespace std; // A utility function to get maximum // value in arr[] int getMax(int arr[], int n) {  int mx = arr[0];  for (int i = 1; i < n; i++)  if (arr[i]>mx) mx = arr[i];  return mx; } // Eine Funktion zum Zählen von arr[] // entsprechend der durch exp dargestellten Ziffer //. void countSort(int arr[], int n, int exp) { // Ausgabearray int output[n];  int i, count[10] = { 0 };  // Anzahl der Vorkommen // in count[] speichern für (i = 0; i< n; i++)  count[(arr[i] / exp) % 10]++;  // Change count[i] so that count[i]  // now contains actual position  // of this digit in output[]  for (i = 1; i < 10; i++)  count[i] += count[i - 1];  // Build the output array  for (i = n - 1; i>= 0; i--) { Output[count[(arr[i] / exp) % 10] - 1] = arr[i];  count[(arr[i] / exp) % 10]--;  } // Kopiere das Ausgabearray nach arr[], // so dass arr[] jetzt sortierte // Zahlen entsprechend der aktuellen Ziffer enthält für (i = 0; i< n; i++)  arr[i] = output[i]; } // The main function to that sorts arr[] // of size n using Radix Sort void radixsort(int arr[], int n) {  // Find the maximum number to  // know number of digits  int m = getMax(arr, n);  // Do counting sort for every digit.  // Note that instead of passing digit  // number, exp is passed. exp is 10^i  // where i is current digit number  for (int exp = 1; m / exp>0; exp *= 10) countSort(arr, n, exp); } // Eine Hilfsfunktion zum Drucken eines Arrays void print(int arr[], int n) { for (int i = 0; i< n; i++)  cout << arr[i] << ' '; } // Driver Code int main() {  int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 };  int n = sizeof(arr) / sizeof(arr[0]);  // Function Call  radixsort(arr, n);  print(arr, n);  return 0; }>

// Radix sort Java implementation import java.io.*; import java.util.*; class Radix {  // A utility function to get maximum value in arr[]  static int getMax(int arr[], int n)  {  int mx = arr[0];  for (int i = 1; i < n; i++)  if (arr[i]>mx) mx = arr[i];  return mx;  } // Eine Funktion zum Zählen von arr[] entsprechend // der durch exp dargestellten Ziffer.  static void countSort(int arr[], int n, int exp) { int output[] = new int[n]; // Ausgabearray int i;  int count[] = new int[10];  Arrays.fill(count, 0);  // Anzahl der Vorkommen in count[] speichern für (i = 0; i< n; i++)  count[(arr[i] / exp) % 10]++;  // Change count[i] so that count[i] now contains  // actual position of this digit in output[]  for (i = 1; i < 10; i++)  count[i] += count[i - 1];  // Build the output array  for (i = n - 1; i>= 0; i--) { Output[count[(arr[i] / exp) % 10] - 1] = arr[i];  count[(arr[i] / exp) % 10]--;  } // Kopiere das Ausgabearray nach arr[], sodass arr[] jetzt // nach der aktuellen // Ziffer sortierte Zahlen enthält für (i = 0; i< n; i++)  arr[i] = output[i];  }  // The main function to that sorts arr[] of  // size n using Radix Sort  static void radixsort(int arr[], int n)  {  // Find the maximum number to know number of digits  int m = getMax(arr, n);  // Do counting sort for every digit. Note that  // instead of passing digit number, exp is passed.  // exp is 10^i where i is current digit number  for (int exp = 1; m / exp>0; exp *= 10) countSort(arr, n, exp);  } // Eine Hilfsfunktion zum Drucken eines Arrays static void print(int arr[], int n) { for (int i = 0; i< n; i++)  System.out.print(arr[i] + ' ');  }  // Main driver method  public static void main(String[] args)  {  int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 };  int n = arr.length;  // Function Call  radixsort(arr, n);  print(arr, n);  } }>

# Python program for implementation of Radix Sort # A function to do counting sort of arr[] according to # the digit represented by exp. def countingSort(arr, exp1): n = len(arr) # The output array elements that will have sorted arr output = [0] * (n) # initialize count array as 0 count = [0] * (10) # Store count of occurrences in count[] for i in range(0, n): index = arr[i] // exp1 count[index % 10] += 1 # Change count[i] so that count[i] now contains actual # position of this digit in output array for i in range(1, 10): count[i] += count[i - 1] # Build the output array i = n - 1 while i>= 0: index = arr[i] // exp1 Output[count[index % 10] - 1] = arr[i] count[index % 10] -= 1 i -= 1 # Kopieren des Ausgabearrays nach arr[] , # sodass arr jetzt sortierte Zahlen i = 0 für i in range(0, len(arr)) enthält: arr[i] = Output[i] # Methode zur Durchführung der Radix-Sortierung def radixSort(arr): # Finden Sie das Maximum Zahl, um die Anzahl der Ziffern zu kennen max1 = max(arr) # Zählsortierung für jede Ziffer durchführen. Beachten Sie, dass anstelle der Nummer der übergebenen Ziffer exp übergeben wird. exp ist 10^i # wobei i die aktuelle Ziffernnummer ist exp = 1 während max1 / exp>= 1: countingSort(arr, exp) exp *= 10 # Treibercode arr = [170, 45, 75, 90, 802, 24 , 2, 66] # Funktionsaufruf radixSort(arr) für i in range(len(arr)): print(arr[i], end=' ') # Dieser Code wurde von Mohit Kumra beigesteuert # Bearbeitet von Patrick Gallagher>

// C# implementation of Radix Sort using System; class GFG {  public static int getMax(int[] arr, int n)  {  int mx = arr[0];  for (int i = 1; i < n; i++)  if (arr[i]>mx) mx = arr[i];  return mx;  } // Eine Funktion zum Zählen von arr[] entsprechend // der durch exp dargestellten Ziffer.  public static void countSort(int[] arr, int n, int exp) { int[] output = new int[n]; // Ausgabearray int i;  int[] count = new int[10];  // Initialisierung aller Elemente von count auf 0 für (i = 0; i< 10; i++)  count[i] = 0;  // Store count of occurrences in count[]  for (i = 0; i < n; i++)  count[(arr[i] / exp) % 10]++;  // Change count[i] so that count[i] now contains  // actual  // position of this digit in output[]  for (i = 1; i < 10; i++)  count[i] += count[i - 1];  // Build the output array  for (i = n - 1; i>= 0; i--) { Output[count[(arr[i] / exp) % 10] - 1] = arr[i];  count[(arr[i] / exp) % 10]--;  } // Kopiere das Ausgabearray nach arr[], sodass arr[] jetzt // nach der aktuellen // Ziffer sortierte Zahlen enthält für (i = 0; i< n; i++)  arr[i] = output[i];  }  // The main function to that sorts arr[] of size n using  // Radix Sort  public static void radixsort(int[] arr, int n)  {  // Find the maximum number to know number of digits  int m = getMax(arr, n);  // Do counting sort for every digit. Note that  // instead of passing digit number, exp is passed.  // exp is 10^i where i is current digit number  for (int exp = 1; m / exp>0; exp *= 10) countSort(arr, n, exp);  } // Eine Hilfsfunktion zum Drucken eines Arrays public static void print(int[] arr, int n) { for (int i = 0; i< n; i++)  Console.Write(arr[i] + ' ');  }  // Driver Code  public static void Main()  {  int[] arr = { 170, 45, 75, 90, 802, 24, 2, 66 };  int n = arr.Length;  // Function Call  radixsort(arr, n);  print(arr, n);  }  // This code is contributed by DrRoot_ }>

// Radix sort JavaScript implementation 'use strict'; // A utility function to get maximum value in arr[] function getMax(arr) {  const length = arr.length;  let mx = arr[0];  for (let i = 1; i < length; i++) {  if (arr[i]>mx) mx = arr[i];  } return mx; } // Eine Funktion zum Zählen von arr[] entsprechend // der durch exp dargestellten Ziffer. function countSort(arr, exp) { const length = arr.length;  let output = Array(length); // Ausgabearray let count = Array(10).fill(0, 0);  // Anzahl der Vorkommen in count[] speichern for (let i = 0; i< length; i++) {  const digit = Math.floor(arr[i] / exp) % 10;  count[digit]++;  }  // Change count[i] so that count[i] now contains  // actual position of this digit in output[]  for (let i = 1; i < 10; i++) {  count[i] += count[i - 1];  }  // Build the output array  for (let i = length - 1; i>= 0; i--) { const digit = Math.floor(arr[i] / exp) % 10;  Ausgabe[Anzahl[Ziffer] - 1] = arr[i];  count[digit]--;  } Ausgabe zurückgeben; } // Die Hauptfunktion zum Sortieren von arr[] mithilfe der Radix-Sort-Funktion radixSort(arr) { // Finden Sie die maximale Anzahl, um die Anzahl der Ziffern zu ermitteln const maxNumber = getMax(arr);  // Eine flache Kopie erstellen, in der die sortierten Werte aufbewahrt werden let sortedArr = [...arr];  // Zählsortierung für jede Ziffer durchführen. Beachten Sie, dass // anstelle der Ziffernnummer exp übergeben wird.  // exp ist 10^i, wobei i die aktuelle Ziffernzahl ist für (let exp = 1; Math.floor(maxNumber / exp)> 0; exp *= 10) { // Holen Sie sich die Count-Sort-Iteration const sortedIteration = countSort(sortedArr , exp);  sortiertArr = sortiertIteration;  } return sortedArr; } /*Treibercode*/ const arr = [170, 45, 75, 90, 802, 24, 2, 66]; // Funktionsaufruf const sortedArr = radixSort(arr); console.log(sortedArr.join(' ')); // Dieser Code wurde von beeduhboodee>'> beigesteuertPHP>

// Radix sort Dart implementation /// A utility function to get the maximum value of a `List` [array] int getMax(List array) { int max = array[0];  for (final it in array) { if (it> max) { max = it;  } } return max; } /// Eine Funktion zum Zählen der Sortierung von „Liste“ [Array] entsprechend der /// Ziffer, die durch [exp] dargestellt wird. Aufführen countSort(Liste array, int exp) { final length = array.length;  endgültige AusgabeArr = List.filled(length, 0);  // Eine Liste, in der der Index die Ziffer und der Wert die Anzahl der // Vorkommen repräsentiert. EndziffernCount = List.filled(10, 0);  // Anzahl der Vorkommen in digitsCount[] speichern for (letztes Element im Array) { final digit = item ~/ exp % 10;  digitsCount[digit]++;  } // DigitsCount[i] ändern, sodass digitsCount[i] jetzt die tatsächliche Position // dieser Ziffer in OutputArr[] enthält for (int i = 1; i< 10; i++) {  digitsCount[i] += digitsCount[i - 1];  }  // Build the output array  for (int i = length - 1; i>= 0; i--) { final item = array[i];  letzte Ziffer = Artikel ~/ exp % 10;  OutputArr[digitsCount[digit] - 1] = item;  digitsCount[digit]--;  } return OutputArr; } /// Die Hauptfunktion zum Sortieren einer „Liste“ [Array] mithilfe der Radix-Sortierliste radixSort(Liste array) { // Finden Sie die maximale Zahl, um die Anzahl der Ziffern zu ermitteln final maxNumber = getMax(array);  // Flache Kopie des Eingabearrays final sortedArr = List.of(array);  // Zählsortierung für jede Ziffer durchführen. Beachten Sie, dass statt der Ziffer // Zahl exp übergeben wird. exp ist 10^i, wobei i die aktuelle Ziffernzahl für (int exp = 1; maxNumber ~/ exp> 0; exp *= 10) { final sortedIteration = countSort(sortedArr, exp);  sortedArr.clear();  sortedArr.addAll(sortedIteration);  } return sortedArr; } void main() { const array = [170, 45, 75, 90, 802, 24, 2, 66];  final sortedArray = radixSort(array);  print(sortedArray); } // Dieser Code wurde von beeduhboodee>'> beigesteuert  
  Ausgabe      Zeitkomplexität:     
 
Die Radix-Sortierung ist ein nicht vergleichender ganzzahliger Sortieralgorithmus, der Daten mit ganzzahligen Schlüsseln sortiert, indem er die Schlüssel nach den einzelnen Ziffern gruppiert, die dieselbe signifikante Position und denselben Wert haben. Es hat eine zeitliche Komplexität von    O(d * (n + b))    , wobei d die Anzahl der Ziffern, n die Anzahl der Elemente und b die Basis des verwendeten Zahlensystems ist.
In praktischen Implementierungen ist die Radix-Sortierung bei großen Datensätzen oft schneller als andere vergleichsbasierte Sortieralgorithmen wie Quicksort oder Merge-Sort, insbesondere wenn die Schlüssel viele Ziffern haben. Allerdings wächst seine zeitliche Komplexität linear mit der Anzahl der Ziffern und ist daher für kleine Datensätze nicht so effizient.
    Hilfsraum:    
 
Die Radix-Sortierung hat auch eine räumliche Komplexität von    O(n + b),    Dabei ist n die Anzahl der Elemente und b die Basis des Zahlensystems. Diese Platzkomplexität ergibt sich aus der Notwendigkeit, für jeden Ziffernwert Buckets zu erstellen und die Elemente nach der Sortierung jeder Ziffer wieder in das ursprüngliche Array zu kopieren.
Häufig gestellte Fragen zu RadixSort
    Q1. Ist Radix Sort vergleichsbasierten Sortieralgorithmen wie Quick-Sort vorzuziehen?     
 
Wenn wir ein Protokoll haben2n Bits für jede Ziffer, die Laufzeit von Radix scheint für einen weiten Bereich von Eingabezahlen besser zu sein als die von Quick Sort. Die in der asymptotischen Notation verborgenen konstanten Faktoren sind für Radix Sort höher und Quick-Sort nutzt Hardware-Caches effektiver. Außerdem verwendet die Radix-Sortierung die Zählsortierung als Unterroutine und die Zählsortierung benötigt zusätzlichen Platz zum Sortieren von Zahlen.
 
    Q2.         Was ist, wenn die Elemente in der         reichen von 1 bis n       2       ?    
 
Die untere Grenze für den vergleichsbasierten Sortieralgorithmus (Merge Sort, Heap Sort, Quick-Sort usw.) ist Ω(nLogn), d. h. sie können nicht besser abschneiden als      nAnmelden      . Counting Sort ist ein linearer Zeitsortieralgorithmus, der in O(n+k)-Zeit sortiert, wenn Elemente im Bereich von 1 bis k liegen.
Wir können die Zählsortierung nicht verwenden, da die Zählsortierung O(n) benötigt2), was schlechter ist als vergleichsbasierte Sortieralgorithmen. Können wir ein solches Array in linearer Zeit sortieren?
    Radix sortieren    ist die Antwort. Die Idee von Radix Sort besteht darin, Ziffer für Ziffer beginnend von der niedrigstwertigen bis zur höchstwertigen Ziffer zu sortieren. Die Radix-Sortierung verwendet die Zählsortierung als Unterroutine zum Sortieren.