当前位置：首页 > news >正文

Java - 基数排序算法介绍、应用场景和示例代码

news 2025/7/14 23:44:37

概述

基数排序（Radix Sort）是一种非比较型整数排序算法，适用于整数或固定长度的字符串排序。它的基本思想是将待排序的元素分为多个关键字进行排序，通常从最低位（最低有效位，Least Significant Digit, LSD）到最高位（最高有效位，Most Significant Digit, MSD）逐位进行排序。

基数排序可以利用计数排序（Counting Sort）或桶排序作为子程序来实现单个位上的排序。这使得基数排序在特定场合下非常高效，能够以线性时间复杂度 O(d⋅(n+k))O(d \cdot (n + k))O(d⋅(n+k)) 完成排序，其中 ddd 是数字的位数，nnn 是数组的元素数量，kkk 是基数（例如 10 对于十进制数）。

算法步骤

确定最大位数：找出数组中最大数的位数（最大数字决定了要排序的轮数）。
逐位排序：从最低有效位（LSD）到最高有效位（MSD）逐位进行排序。
使用稳定排序算法：通常使用计数排序来保证每个位上的排序是稳定的。

应用场景

基数排序适用于需要对大规模整数数据进行排序的场合，尤其是当数值位数较小时。它常用于电话号码、身份证号等固定长度的数字或字符串排序。在不要求原地排序的情况下，基数排序可以高效地处理大规模数据集。

算法特点

时间复杂度：O(d⋅(n+k))O(d \cdot (n + k))O(d⋅(n+k))，其中 ddd 是数字的位数，kkk 是基数。
空间复杂度：需要额外的空间用于计数排序，因此空间复杂度为 O(n+k)O(n + k)O(n+k)。
稳定性：是稳定的排序算法，因为使用稳定的子排序算法。

示例代码

下面是一个用 Java 实现的基数排序示例代码，针对整数数组：

import java.util.Arrays;public class RadixSort {// 获取数组中的最大值，用于确定最大位数private static int getMax(int[] arr) {int max = arr[0];for (int num : arr) {if (num > max) {max = num;}}return max;}// 对数组的某个位进行计数排序private static void countingSort(int[] arr, int exp) {int n = arr.length;int[] output = new int[n];int[] count = new int[10]; // 基数是10// 统计出现的次数for (int num : arr) {int index = (num / exp) % 10;count[index]++;}// 更新计数数组，计算累计计数for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}// 构建输出数组for (int i = n - 1; i >= 0; i--) {int num = arr[i];int index = (num / exp) % 10;output[count[index] - 1] = num;count[index]--;}// 将排序结果复制回原数组System.arraycopy(output, 0, arr, 0, n);}// 基数排序主函数public static void radixSort(int[] arr) {int max = getMax(arr);// 从最低有效位开始排序for (int exp = 1; max / exp > 0; exp *= 10) {countingSort(arr, exp);}}public static void main(String[] args) {int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};System.out.println("排序前数组:");System.out.println(Arrays.toString(arr));radixSort(arr);System.out.println("排序后数组:");System.out.println(Arrays.toString(arr));}
}