Java 基数排序算法
最后修改时间：2025 年 4 月 16 日
排序算法简介
算法是解决问题或执行计算的逐步过程。排序算法将元素按特定顺序排列，通常是升序或降序。高效的排序对于优化其他算法至关重要。
常见的排序算法包括
- 冒泡排序 - 简单但效率低下的 O(n²) 算法
- 选择排序 - 另一个 O(n²) 算法，交换次数更少
- 插入排序 - 对于小型或近乎排序的数据效率很高
- 归并排序 - 具有 O(n log n) 性能的分而治之算法
- 快速排序 - 平均情况下的快速 O(n log n) ，最坏情况为 O(n²)
- 堆排序 - 使用二叉堆的 O(n log n) 排序
- 基数排序 - 非比较整数排序算法
理解基数排序
基数排序是一种非比较整数排序算法，它处理数字。它通过处理个别数字，从最低有效位 (LSD) 到最高有效位 (MSD) 或反之亦然，来对数字进行排序。基数排序的时间复杂度为 O(nk)。
基数排序的关键特性
- 适用于整数、字符串或任何带有数字/字符的数据
- 使用计数排序作为子程序
- 稳定排序（保留相等元素的原始顺序）
- 当 k（数字的位数）较小时，表现良好
数字的基数排序实现
这是一个 Java 实现的整数基数排序。此版本从最低有效位到最高有效位（LSD 基数排序）处理数字。
RadixSort.java
package com.zetcode;
public class RadixSort {
// Main method to perform radix sort
public static void radixSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
// Find the maximum number to know number of digits
int max = getMax(arr);
// Do counting sort for every digit
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, exp);
}
}
// Utility method to get maximum value in array
private static int getMax(int[] arr) {
int max = arr[0];
for (int num : arr) {
if (num > max) {
max = num;
}
}
return max;
}
// Counting sort for a specific digit (exp)
private static void countingSort(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
// Store count of occurrences in count[]
for (int num : arr) {
count[(num / exp) % 10]++;
}
// Change count[i] to contain actual position
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// Build the output array
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// Copy the output array to arr[]
System.arraycopy(output, 0, arr, 0, n);
}
public static void main(String[] args) {
int[] data = {170, 45, 75, 90, 802, 24, 2, 66};
System.out.println("Original array:");
for (int num : data) {
System.out.print(num + " ");
}
radixSort(data);
System.out.println("\nSorted array (ascending):");
for (int num : data) {
System.out.print(num + " ");
}
}
}
此实现首先找到最大数字以确定所需的位数。然后，它从最低有效位到最高有效位对每个数字位置执行计数排序。排序后的数组在每次传递中构建。
降序排序
要以降序排序，我们可以修改计数排序步骤以按相反顺序构建输出数组。 这是修改后的版本
RadixSortDescending.java
package com.zetcode;
public class RadixSortDescending {
public static void radixSortDescending(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
int max = getMax(arr);
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSortDescending(arr, exp);
}
}
private static int getMax(int[] arr) {
int max = arr[0];
for (int num : arr) {
if (num > max) {
max = num;
}
}
return max;
}
private static void countingSortDescending(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
for (int num : arr) {
count[9 - (num / exp) % 10]++; // Modified for descending
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
output[count[9 - (arr[i] / exp) % 10] - 1] = arr[i];
count[9 - (arr[i] / exp) % 10]--;
}
System.arraycopy(output, 0, arr, 0, n);
}
public static void main(String[] args) {
int[] data = {170, 45, 75, 90, 802, 24, 2, 66};
System.out.println("Original array:");
for (int num : data) {
System.out.print(num + " ");
}
radixSortDescending(data);
System.out.println("\nSorted array (descending):");
for (int num : data) {
System.out.print(num + " ");
}
}
}
关键的变化是在 countingSortDescending 方法中，我们使用 9 - (num / exp) % 10 而不是仅仅使用 (num / exp) % 10。 这反转了计数期间的数字顺序，从而导致降序排序。
字符串的基数排序
基数排序也可以按字典顺序对字符串进行排序。每个字符位置都被视为一个数字。 这是一个用于排序字符串的实现
StringRadixSort.java
package com.zetcode;
public class StringRadixSort {
public static void radixSort(String[] arr) {
if (arr == null || arr.length == 0) {
return;
}
// Find the maximum length string
int maxLength = getMaxLength(arr);
// Perform counting sort for each character position
for (int pos = maxLength - 1; pos >= 0; pos--) {
countingSort(arr, pos);
}
}
private static int getMaxLength(String[] arr) {
int max = arr[0].length();
for (String s : arr) {
if (s.length() > max) {
max = s.length();
}
}
return max;
}
private static void countingSort(String[] arr, int pos) {
int n = arr.length;
String[] output = new String[n];
int[] count = new int[256]; // ASCII range
// Count occurrences
for (String s : arr) {
int index = (pos < s.length()) ? s.charAt(pos) : 0;
count[index]++;
}
// Compute cumulative counts
for (int i = 1; i < 256; i++) {
count[i] += count[i - 1];
}
// Build output array
for (int i = n - 1; i >= 0; i--) {
String s = arr[i];
int index = (pos < s.length()) ? s.charAt(pos) : 0;
output[count[index] - 1] = s;
count[index]--;
}
// Copy back to original array
System.arraycopy(output, 0, arr, 0, n);
}
public static void main(String[] args) {
String[] data = {"apple", "banana", "kiwi", "orange", "grape", "pear"};
System.out.println("Original array:");
for (String s : data) {
System.out.print(s + " ");
}
radixSort(data);
System.out.println("\nSorted array (ascending):");
for (String s : data) {
System.out.print(s + " ");
}
}
}
此实现从右到左（MSD 基数排序）处理字符串。 较短的字符串被视为在缺失位置具有空字符 (ASCII 0)。 该排序是稳定的，并保持相等字符串的相对顺序。
性能比较：基数排序 vs 快速排序
基数排序和快速排序具有不同的性能特征。 基数排序在 O(nk) 时间内执行，其中 n 是元素数量，k 是数字位数。 快速排序平均为 O(n log n)，但在最坏情况下会降低到 O(n²)。
让我们通过基准测试比较它们的性能
SortBenchmark.java
package com.zetcode;
import java.util.Arrays;
import java.util.Random;
public class SortBenchmark {
public static void main(String[] args) {
int size = 1000000;
int[] radixData = generateRandomArray(size);
int[] quickData = Arrays.copyOf(radixData, radixData.length);
// Radix Sort benchmark
long start = System.currentTimeMillis();
radixSort(radixData);
long radixTime = System.currentTimeMillis() - start;
// QuickSort benchmark
start = System.currentTimeMillis();
Arrays.sort(quickData);
long quickTime = System.currentTimeMillis() - start;
System.out.println("Radix Sort time: " + radixTime + " ms");
System.out.println("QuickSort time: " + quickTime + " ms");
}
private static int[] generateRandomArray(int size) {
Random random = new Random();
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = random.nextInt(1000000);
}
return arr;
}
// Main method to perform radix sort
private static void radixSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
// Find the maximum number to know number of digits
int max = getMax(arr);
// Do counting sort for every digit
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, exp);
}
}
// Utility method to get maximum value in array
private static int getMax(int[] arr) {
int max = arr[0];
for (int num : arr) {
if (num > max) {
max = num;
}
}
return max;
}
// Counting sort for a specific digit (exp)
private static void countingSort(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
// Store count of occurrences in count[]
for (int num : arr) {
count[(num / exp) % 10]++;
}
// Change count[i] to contain actual position
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// Build the output array
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// Copy the output array to arr[]
System.arraycopy(output, 0, arr, 0, n);
}
}
这个 Java 程序基准测试了两种排序算法的性能：基数排序和快速排序。 它生成一个大的随机整数数组，使用两种算法对数组进行排序，并测量每种算法排序所需的时间。 基数排序是手动实现的，侧重于基于数字的排序，而快速排序使用 Java 内置的 Arrays.sort 方法。 该程序输出排序时间以进行比较，使其有助于理解算法效率。
典型结果可能显示
- 对于小范围（小 k），基数排序通常优于快速排序
- 对于大范围，快速排序通常表现更好
- 基数排序使用更多内存（O(n+k) vs 快速排序的 O(log n) 堆栈空间）
- 快速排序是基于比较的，适用于任何可比较的数据
何时使用基数排序
当以下情况时，基数排序特别有效
- 对具有有限值范围的整数进行排序
- 对固定长度的字符串或具有一致的数字/字符计数的数据进行排序
- 需要排序的稳定性
- 您可以牺牲内存使用来换取速度
通常首选快速排序，当
- 对任意可比较对象进行排序
- 内存受到限制
- 数据具有大范围的可能值
来源
在本教程中，我们介绍了 Java 中的基数排序算法，包括升序和降序的数值和文本数据的实现。 我们还将它的性能与快速排序进行了比较。
作者
列出所有Java教程。