排序算法：基数排序

本文主要是介绍排序算法：基数排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1，基数排序基本介绍

基数排序（Radix Sort）属于分配式排序，又称桶子法或者Bin Sort，它是通过键值的各个位的值，将要排序的数组分配到对应桶中，达到排序的左右
基数排序属于稳定性排序，同时也是效率较高的稳定性排序，基数排序是对桶排序的扩展
基数排序基本思想：将所有待比较的数值统一为同样的数位长度（长度不足前位补零）；然后，从低位开始，依次进行一次排序。按照基本排序规则，等所有位数全部比较完成后，数据就是一个有序数列
- 首先初始化一个二维数组，第一维表示桶的个数，从0-9共有10个桶，第二维表示落到桶中的数据
- 其次初始化一个长度为10的一维数组，索引表示0-9的9个桶，值表示落到桶中的数据数量，用于计数
- 从这一步开始真正进行基数排序处理，对要处理的数组元素依次截取个位数，并按照个位数数字对应落到二维数组初始化的0-9的对应桶中，并用一维数据进行计数
- 这一轮处理完成后，依次从二维数组中获取所有数据，对原数组进行覆盖，此时即完成第一轮循环，这一步处理完成后记得对一维数据组清零
- 依次类推，个位数处理完成后处理十位，百位，直到处理到数组中最大元素的最高位，最高位处理完成后，覆盖原数组，此时数组有序
注意：基数排序理论上来讲只能对正数进行排序；存在负数的数组中，可以先对整个数组+最小负数，此时数组最小为0，然后再对该数组进行基数排序，排序完成后再对全数组-最小负数，则完成对数组排序

2，基数排序示例

将数组{53，3，542，748，14，214}进行基数排序，因为最大数 748 的最高位数为三位，则需要进行三轮处理，流程如下：
第一轮处理：对个位数进行处理
第二轮处理：对十位数进行处理
第三轮处理：对百位数进行处理

3，基数排序代码实现

package com.self.datastructure.sort;/*** 基数排序** @author PJ_ZHANG* @create 2020-03-13 10:24**/
public class RadixSort {public static void main(String[] args) {
//        int[] array = {45, 832, 456, 76, 32, 17, 89, 456, 56};// 10万个数测试, 52ms// 100万测试, 208ms// 1000万测试, 1265ms// 1E测试, 8609ms, -Xmx9000m(4096M没够用)int[] array = new int[100000000];for (int i = 0; i < 100000000; i++) {array[i] = (int) (Math.random() * 8000000);}long startTime = System.currentTimeMillis();radixSort(array);
//        System.out.println(Arrays.toString(array));System.out.println("cast time : " + (System.currentTimeMillis() - startTime));}/*** 基数排序基本流程* * 初始化一个二维数组, 第一维表示0-9的10个元素桶, 第二维表示落到桶中的数据* * 初始化一个一维数组, 下标表示0-9是个数字, 值表示落到桶中数据的数量* * 对要排序的数组依次从个位开始截取处理, 按个位数据落到对应的二维桶中, 并用一维数组进行计数* * 一轮位数处理完成后, 从二维数据中依次取出所有数据, 对原数据进行覆盖* * 每一轮处理完成后, 记得对一维数据进行置空* @param array*/private static void radixSort(int[] array) {// 二维数组存储数据int[][] dataArray = new int[10][array.length];// 一维数据计数int[] countArray = new int[10];int maxCount = 0;for (int i = 0; i < array.length; i++) {if (array[i] > maxCount) {maxCount = array[i];}}// round表示当前取的是哪一位, 用位数的整值表示, 比如十位是10, 百位是100// 基数排序, 按照最大数的最高位数进行循环for (int i = 0, round = 1; i < (maxCount + "").length(); i++, round *= 10) {// 将数据放入到对应的桶中, 即二维数组中for (int j = 0; j < array.length; j++) {// 获取位数值int data = array[j] / round  % 10;// 存储当前值到二维数据// 并对一维数据数据统计值递增dataArray[data][countArray[data]++] = array[j];}int index = 0;// 先从一维数据中获取到存在有效数据的二维数据部分for (int countIndex = 0; countIndex < countArray.length; countIndex++) {// 为0, 表示当前桶中不存在数据if (countArray[countIndex] == 0) continue;// 从二维数据获取到有效数据, 存储到原数组中for (int dataIndex = 0; dataIndex < countArray[countIndex]; dataIndex++) {array[index++] = dataArray[countIndex][dataIndex];}// 统计数组处理完成后, 对统计数量置空countArray[countIndex] = 0;}}}}