网站开发天晟合益,wordpress发文章设置文字大小,网站设计教程文档,wordpress改主题幻灯片尺寸基数排序#xff08;Radix Sort#xff09;是一种非比较型整数排序算法#xff0c;通常用于对数字进行排序。它按照数字的每一位#xff08;从最低有效位到最高有效位或从最高有效位到最低有效位#xff09;进行排序#xff0c;每次使用一个稳定的排序算法#xff08;如…基数排序Radix Sort是一种非比较型整数排序算法通常用于对数字进行排序。它按照数字的每一位从最低有效位到最高有效位或从最高有效位到最低有效位进行排序每次使用一个稳定的排序算法如计数排序或桶排序对相应位进行排序。
以下是基数排序的一个基本实现这里我们使用计数排序作为子排序算法并假设我们要排序的是非负整数
import java.util.Arrays; public class RadixSort { // 获取数组中最大值 private static int getMax(int[] array) { int max array[0]; for (int num : array) { if (num max) { max num; } } return max; } // 计数排序用于对指定位的数字进行排序 private static void countingSort(int[] array, int exp) { int n array.length; int[] output new int[n]; // 输出数组 int[] count new int[10]; // 假设数字在0到9之间 Arrays.fill(count, 0); // 统计每个桶中的数字个数 for (int i 0; i n; i) { count[(array[i] / exp) % 10]; } // 修改count数组使其包含位置信息 for (int i 1; i 10; i) { count[i] count[i - 1]; } // 构建输出数组 for (int i n - 1; i 0; i--) { output[count[(array[i] / exp) % 10] - 1] array[i]; count[(array[i] / exp) % 10]--; } // 将排序结果复制回原数组 System.arraycopy(output, 0, array, 0, n); } // 基数排序主函数 public static void radixSort(int[] array) { // 找到最大数确定最大位数 int max getMax(array); // 从个位开始对每一位进行计数排序 for (int exp 1; max / exp 0; exp * 10) { countingSort(array, exp); } } public static void main(String[] args) { int[] array {170, 45, 75, 90, 802, 24, 2, 66}; System.out.println(排序前: Arrays.toString(array)); radixSort(array); System.out.println(排序后: Arrays.toString(array)); }
}
代码说明
getMax函数找到数组中的最大值用于确定最大位数。countingSort函数实现计数排序对数组按指定的位数由参数exp决定进行排序。exp是10的幂次表示当前排序的位数个位、十位、百位等。radixSort函数基数排序的主函数从个位开始依次对每一位进行计数排序。main函数测试基数排序算法。
运行结果
排序前: [170, 45, 75, 90, 802, 24, 2, 66]
排序后: [2, 24, 45, 66, 75, 90, 170, 802]
基数排序的时间复杂度为O(d * (n k))其中d是数字的最大位数n是数组的长度k是计数排序的桶的数量对于十进制数k通常为10。这使得基数排序在处理大量数字时非常高效尤其是当数字位数较大时。
