Java基数排序

基数排序图示

  基数排序（radix sort）是一种 非比较型 排序算法，属于“分配式排序”（distribution sort），一般用于排序正整数序列，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。   基数排序（radix sort）是桶排序的升级版。

实现思路：

首先需要定义一个二维数组长度为 10 代表 0~9，宽度为待排序数组的长度。找到待排序数组中的最大值，获取最大数的位数，这决定了需要进行多少轮排序。排序从个位开始，依次向前递增，根据对应位数的值决定该数放入哪个桶中。一轮排序结束后，需要将桶中的数据依次取出，放入原数组。

---

参考代码

public static void radixSort(int[] arr) { // 二维数组，存放 10 个桶和各桶中的元素 int[][] bucket = new int[10][arr.length]; // 一维数组，记录每个桶中元素的个数 int[] elementCounts = new int[10]; // 获取待排序数组中最大数 int max = 0; for (int num : arr) { if (max < num) max = num; } // 获取最大数的位数 ==> 转成字符串求长度 int digits = ("" + max).length(); // 排序，K 为当前比较位数，个、十、百、千... for (int i = 0, k = 1; i < digits; i++, k *= 10) { // 将 arr 中的数据按规则放入桶中 for (int num : arr) { int m = num / k % 10; // 第 m 个桶 int n = elementCounts[m]; // 第 m 个桶中的第 n 个位置 bucket[m][n] = num; elementCounts[m]++; } // 将桶中的数据依次放回 arr 中，进行下一轮排序 int index = 0; for (int j = 0; j < 10; j++) { // 一共 10 个桶 if (elementCounts[j] == 0) continue; // 如果第 j 个桶中的元素个数为 0，换下一个桶 for (int l = 0; l < elementCounts[j]; l++) { arr[index] = bucket[j][l]; index++; } elementCounts[j] = 0; // 元素个数清零 } } }

---

排序效果测试

public static void main(String[] args) { int[] arr = {1, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}; System.out.println("排序前：" + Arrays.toString(arr)); radixSort(arr); System.out.println("基数排序：" + Arrays.toString(arr)); }

---

1000 万随机数据测试排序时间

public static void main(String[] args) { int[] arrTime = new int[10000000]; for (int i = 0; i < 10000000; i++) { arrTime[i] = (int) (Math.random() * 10000000); } long former = System.currentTimeMillis(); radixSort(arrTime); long later = System.currentTimeMillis(); System.out.println("时间：" + (later - former) + " 毫秒"); }

基数排序十分消耗内存，1亿数据会直接报错 java.lang.OutOfMemoryError: Java heap space一般用于排序正整数序列，如果要处理含负数和小数的情况，需要再增加桶。