上查看所有课程
基数排序是一种排序算法，它首先根据相同位值的单个数字对元素进行分组，然后根据这些元素的升序/降序对其进行排序。
假设我们有一个包含 8 个元素的数组。首先，我们将根据个位值对元素进行排序。然后，我们将根据十位值对元素进行排序。这个过程将一直持续到最后一个有效位。
设初始数组为 [121, 432, 564, 23, 1, 45, 788]。如下图所示，它通过基数排序进行排序。
在阅读本文之前，请先了解计数排序，因为计数排序在基数排序中用作中间排序。
基数排序的工作原理
- 找到数组中的最大元素，即 max。设
X为max中的数字位数。计算X是因为我们需要遍历所有元素的有效位。
在这个数组[121, 432, 564, 23, 1, 45, 788]中，最大数字是 788。它有 3 位数。因此，循环应持续到百位（3 次）。 - 现在，逐一遍历每个有效位。
使用任何稳定的排序技术对每个有效位的数字进行排序。我们在这里使用了计数排序。
根据个位数字（X=0）对元素进行排序。
使用计数排序根据个位对元素进行排序 - 现在，根据十位数字对元素进行排序。
根据十位对元素进行排序 - 最后，根据百位数字对元素进行排序。
根据百位对元素进行排序
基数排序算法
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 1Python、Java 和 C/C++ 中的基数排序代码
# 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 cumulative 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)// Radix Sort in Java Programming
public class RadixSort {
// Using counting sort to sort the elements based on significant places
public static void countingSort(int[] array, int place) {
int size = array.length;
int[] output = new int[size];
int[] count = new int[10];
// Calculate count of elements
for (int i = 0; i < size; i++) {
int index = (array[i] / place) % 10;
count[index]++;
}
// Calculate cumulative 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--) {
int index = (array[i] / place) % 10;
output[count[index] - 1] = array[i];
count[index]--;
}
// Copy the sorted elements into original array
for (int i = 0; i < size; i++) {
array[i] = output[i];
}
}
// Main function to implement radix sort
public static void radixSort(int[] array) {
// Get maximum element
int maxElement = getMax(array);
// Apply counting sort to sort elements based on place value
for (int place = 1; maxElement / place > 0; place *= 10) {
countingSort(array, place);
}
}
// A utility function to get the maximum value in the array
public static int getMax(int[] array) {
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
}
return max;
}
public static void main(String[] args) {
int[] data = {121, 432, 564, 23, 1, 45, 788};
radixSort(data);
System.out.println("Sorted Array in Ascending Order: ");
for (int num : data) {
System.out.print(num + " ");
}
}
}
// Radix Sort in C Programming
#include <stdio.h>
// Function to get the maximum value in the 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 based on significant places
void countingSort(int array[], int n, int place) {
int output[n];
int count[10] = {0};
// Calculate count of elements
for (int i = 0; i < n; i++) {
int index = (array[i] / place) % 10;
count[index]++;
}
// Calculate cumulative count
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// Place the elements in sorted order
for (int i = n - 1; i >= 0; i--) {
int index = (array[i] / place) % 10;
output[count[index] - 1] = array[i];
count[index]--;
}
// Copy the sorted elements into original array
for (int i = 0; i < n; i++) {
array[i] = output[i];
}
}
// Main function to implement radix sort
void radixSort(int array[], int n) {
// Get maximum element
int maxElement = getMax(array, n);
// Apply counting sort to sort elements based on place value
for (int place = 1; maxElement / place > 0; place *= 10) {
countingSort(array, n, place);
}
}
int main() {
int data[] = {121, 432, 564, 23, 1, 45, 788};
int n = sizeof(data) / sizeof(data[0]);
radixSort(data, n);
printf("Sorted array in ascending order:\n");
for (int i = 0; i < n; i++) {
printf("%d ", data[i]);
}
return 0;
}
// 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 cumulative 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(n+k) |
| 最坏 | O(n+k) |
| 平均 | O(n+k) |
| 空间复杂度 | O(max) |
| 稳定性 | 是 |
由于基数排序是一种非比较排序算法，因此它比比较排序算法具有优势。
对于将计数排序用作中间稳定排序的基数排序，其时间复杂度为 O(d(n+k))。
其中，d 是循环次数，O(n+k) 是计数排序的时间复杂度。
因此，基数排序具有线性时间复杂度，优于比较排序算法的 O(nlog n)。
如果我们处理非常大的数字或具有不同基数的数字，例如 32 位和 64 位数字，它可以以线性时间运行，但中间排序会占用大量空间。
这使得基数排序在空间方面效率低下。这就是为什么此排序未在软件库中使用。
基数排序的应用
基数排序在以下方面有应用：
- DC3 算法（Kärkkäinen-Sanders-Burkhardt）在构建后缀数组时。
- 数字范围很大的地方。