# 基數排序算法 > 原文： [https://www.programiz.com/dsa/radix-sort](https://www.programiz.com/dsa/radix-sort) #### 在本教程中，您將學習基數排序的工作原理。 此外，您還將找到 C，C++ ，Java 和 Python 中基數排序的工作示例。 基數排序是一種排序技術，它通過首先對相同**位置值**的各個數字進行分組來對元素進行排序。 然后，根據元素的升序/降序對元素進行排序。 假設我們有 8 個元素組成的數組。 首先，我們將基于單位位置的值對元素進行排序。 然后，我們將根據第十位的值對元素進行排序。 這個過程一直持續到最后一個重要位置。 令初始數組為`[121, 432, 564, 23, 1, 45, 788]`。 如下圖所示，根據基數排序。  基數排序的原理 在閱讀本文之前，請先閱讀[計數排序](/dsa/counting-sort)，因為計數排序用作基數排序的中間排序。 * * * ## 基數排序如何工作？ 1. 找到數組中最大的元素，即`max`。 令`X`為`max`中的位數。 計算`X`是因為我們必須遍歷所有元素的所有重要位置。 在此數組`[121, 432, 564, 23, 1, 45, 788]`中，我們擁有最大的數字 788。它具有 3 位數字。 因此，循環應上升到百位（3 次）。 2. 現在，一個接一個地訪問每個重要的地方。 使用任何穩定的排序技術在每個重要位置對數字進行排序。 我們為此使用了計數排序。 根據單位位置數字（`X=0`）對元素進行排序。  使用計數排序對基于單位位置的元素進行排序 3. 現在，基于十位數字對元素進行排序。  根據十位對元素進行排序 4. 最后，根據百位數字對元素進行排序。  根據數百個位置對元素進行排序 * * * ## 基數排序算法 ``` radixSort(array) d <- maximum number of digits in the largest element create d buckets of size 0-9 for i <- 0 to d sort the elements according to ith place digits using countingSort countingSort(array, d) max <- find largest element among dth place elements initialize count array with all zeros for j <- 0 to size find the total count of each unique digit in dth place of elements and store the count at jth index in count array for i <- 1 to max find the cumulative sum and store it in count array itself for j <- size down to 1 restore the elements to array decrease count of each element restored by 1 ``` * * * ## Python，Java 和 C/C++ 示例 ```py # Radix sort in Python # Using counting sort to sort the elements in the basis of significant places def countingSort(array, place): size = len(array) output = [0] * size count = [0] * 10 # Calculate count of elements for i in range(0, size): index = array[i] // place count[index % 10] += 1 # Calculate cummulative count for i in range(1, 10): count[i] += count[i - 1] # Place the elements in sorted order i = size - 1 while i >= 0: index = array[i] // place output[count[index % 10] - 1] = array[i] count[index % 10] -= 1 i -= 1 for i in range(0, size): array[i] = output[i] # Main function to implement radix sort def radixSort(array): # Get maximum element max_element = max(array) # Apply counting sort to sort elements based on place value. place = 1 while max_element // place > 0: countingSort(array, place) place *= 10 data = [121, 432, 564, 23, 1, 45, 788] radixSort(data) print(data) ``` ```java // Radix Sort in Java Programming import java.util.Arrays; class RadixSort { // Using counting sort to sort the elements in the basis of significant places void countingSort(int array[], int size, int place) { int[] output = new int[size + 1]; int max = array[0]; for (int i = 1; i < size; i++) { if (array[i] > max) max = array[i]; } int[] count = new int[max + 1]; for (int i = 0; i < max; ++i) count[i] = 0; // Calculate count of elements for (int i = 0; i < size; i++) count[(array[i] / place) % 10]++; // Calculate cummulative count for (int i = 1; i < 10; i++) count[i] += count[i - 1]; // Place the elements in sorted order for (int i = size - 1; i >= 0; i--) { output[count[(array[i] / place) % 10] - 1] = array[i]; count[(array[i] / place) % 10]--; } for (int i = 0; i < size; i++) array[i] = output[i]; } // Function to get the largest element from an array int getMax(int array[], int n) { int max = array[0]; for (int i = 1; i < n; i++) if (array[i] > max) max = array[i]; return max; } // Main function to implement radix sort void radixSort(int array[], int size) { // Get maximum element int max = getMax(array, size); // Apply counting sort to sort elements based on place value. for (int place = 1; max / place > 0; place *= 10) countingSort(array, size, place); } // Driver code public static void main(String args[]) { int[] data = { 121, 432, 564, 23, 1, 45, 788 }; int size = data.length; RadixSort rs = new RadixSort(); rs.radixSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); } } ``` ```c // Radix Sort in C Programming #include <stdio.h> // Function to get the largest element from an array int getMax(int array[], int n) { int max = array[0]; for (int i = 1; i < n; i++) if (array[i] > max) max = array[i]; return max; } // Using counting sort to sort the elements in the basis of significant places void countingSort(int array[], int size, int place) { int output[size + 1]; int max = (array[0] / place) % 10; for (int i = 1; i < size; i++) { if (((array[i] / place) % 10) > max) max = array[i]; } int count[max + 1]; for (int i = 0; i < max; ++i) count[i] = 0; // Calculate count of elements for (int i = 0; i < size; i++) count[(array[i] / place) % 10]++; // Calculate cummulative count for (int i = 1; i < 10; i++) count[i] += count[i - 1]; // Place the elements in sorted order for (int i = size - 1; i >= 0; i--) { output[count[(array[i] / place) % 10] - 1] = array[i]; count[(array[i] / place) % 10]--; } for (int i = 0; i < size; i++) array[i] = output[i]; } // Main function to implement radix sort void radixsort(int array[], int size) { // Get maximum element int max = getMax(array, size); // Apply counting sort to sort elements based on place value. for (int place = 1; max / place > 0; place *= 10) countingSort(array, size, place); } // Print an array void printArray(int array[], int size) { for (int i = 0; i < size; ++i) { printf("%d ", array[i]); } printf("\n"); } // Driver code int main() { int array[] = {121, 432, 564, 23, 1, 45, 788}; int n = sizeof(array) / sizeof(array[0]); radixsort(array, n); printArray(array, n); } ``` ```cpp // Radix Sort in C++ Programming #include <iostream> using namespace std; // Function to get the largest element from an array int getMax(int array[], int n) { int max = array[0]; for (int i = 1; i < n; i++) if (array[i] > max) max = array[i]; return max; } // Using counting sort to sort the elements in the basis of significant places void countingSort(int array[], int size, int place) { const int max = 10; int output[size]; int count[max]; for (int i = 0; i < max; ++i) count[i] = 0; // Calculate count of elements for (int i = 0; i < size; i++) count[(array[i] / place) % 10]++; // Calculate cummulative count for (int i = 1; i < max; i++) count[i] += count[i - 1]; // Place the elements in sorted order for (int i = size - 1; i >= 0; i--) { output[count[(array[i] / place) % 10] - 1] = array[i]; count[(array[i] / place) % 10]--; } for (int i = 0; i < size; i++) array[i] = output[i]; } // Main function to implement radix sort void radixsort(int array[], int size) { // Get maximum element int max = getMax(array, size); // Apply counting sort to sort elements based on place value. for (int place = 1; max / place > 0; place *= 10) countingSort(array, size, place); } // Print an array void printArray(int array[], int size) { int i; for (i = 0; i < size; i++) cout << array[i] << " "; cout << endl; } // Driver code int main() { int array[] = {121, 432, 564, 23, 1, 45, 788}; int n = sizeof(array) / sizeof(array[0]); radixsort(array, n); printArray(array, n); } ``` * * * ## 復雜度 由于基數排序是一種非比較算法，因此它比比較排序算法具有優勢。 對于使用計數排序作為中間穩定排序的基數排序，時間復雜度為`O(d(n+k))`。 此處，`d`是數字循環，`O(n+k)`是計數排序的時間復雜度。 因此，基數排序具有線性時間復雜度，該復雜度優于比較排序算法的`O(nlog n)`。 如果我們使用非常大的數字或其他基數（例如 32 位和 64 位數字），那么它可以在線性時間內執行，但是中間排序會占用很大的空間。 這使得基數排序空間效率低下。 這就是為什么在軟件庫中不使用這種排序的原因。 * * * ## 基數排序應用 基數排序在 * 制作后綴數組時使用 DC3 算法（K?rkk?inen-Sanders-Burkhardt）。 * 大范圍數字的地方。