三、排序算法
基数排序（Radix Sort）
（1）什么是基数排序？
基数排序是桶排序的扩展，其将 整数 按照 位数（个位、十位、百位等）进行划分，每次划分后将划分的结果存放到相应的桶中，最终达到排序的目的。
基数排序属于稳定排序。
【基数排序步骤：(此时无法处理负数)】Step1：首先定义一个桶数组，编号为 0 ~ 9，分别表示用于存储符合 0 ~ 9 的数据。且每个桶元素 又是一个数组，用于存储符合 0 ~ 9 的数据。Step2：对于一组数据，从每个数的 个位 开始进行划分（个位范围为 0 ~ 9），将数据分别存储到 桶数组中。然后遍历输出得到新的数组。Step3：对于新的一组数据，从每个数的 十位 开始划分，进行 Step2 同样操作。Step4：同理，处理 百位、千位，若一个数没有 百位、千位，则将其视为 0 处理。
注：首先得获取当前数据中 最大数据 的位数，然后再进行 位数划分。比如： 7 99 10 8 中最大数据为 两位数，需进行 个位、十位 划分。45 123 34 中最大数据为 三位数，需进行 个位、十位、百位 划分。 【基数排序存在 负数 时处理：】可以先找到 负数的最小值，然后将所有数据 整体加上 负数最小值的绝对值 加 1，记为 min = |负数最小值|，即 让所有数据均变为 非负数，然后再去排序，最后将结果 再整体减去 min 即可。
注：若 最大值、最小值 濒临极限时，可能会造成数据溢出（此时慎用）。 【给数据 arr {38, 65, 97, 76, 13, 27, 49} 排序，并按照从小到大的顺序输出】
Step1：首先定义一个 二维数组 a[10][arr.length] 表示桶，分别用于存储符合 0 ~ 9 的数据。Step2：按照 个位 进行划分。38 个位为 8，进入 a[8] 桶。65 个位为 5，进入 a[5] 桶。97 个位为 7，进入 a[7] 桶。76 个位为 6，进入 a[6] 桶。13 个位为 3，进入 a[3] 桶。27 个位为 7，进入 a[7] 桶。49 个位为 9，进入 a[9] 桶。
即：0123 1345 656 76 7 97 278 389 49依次取出桶中元素，存入新数组中。即 {13, 65, 76, 97, 27, 38, 49}Step3：根据新数组按照 十位 进行划分。13 十位为 1，进入 a[1] 桶。65 十位为 6，进入 a[6] 桶。76 十位为 7，进入 a[7] 桶。97 十位为 9，进入 a[9] 桶。27 十位为 2，进入 a[2] 桶。38 十位为 3，进入 a[3] 桶。49 十位为 4，进入 a[4] 桶。
即：01 132 273 384 4956 657 7689 97依次取出桶中元素，存入新数组中。即 {13, 27, 38, 49, 65, 76, 97}（2）代码实现
【代码实现：】
package com.lyh.sort;import java.util.Arrays;public class RadixSort {public static void main(String[] args) {int[] arrays = new int[]{38, 65, 97, 76, 13, 27, 49};radixSort(arrays);System.out.println("====================");
// int[] arrays = new int[]{38, 65, 0, -1, 13, 27, 49};int[] arrays2 = new int[]{38, 65, 0, -1, 13, 27, -10};radixSort(arrays2);}/*** 基数排序（包括负数排序）* @param arrays 待排序数组*/public static void radixSort(int[] arrays) {// 判断数组是否合法if (arrays.length <= 0) {System.out.println("数据为空");return;}// 获取当前数据中最大值、最小值int max = arrays[0];int min = arrays[0];for (int array : arrays) {if (max < array) {max = array;}if (min > array) {min = array;}}// min 小于 0，即当前存在负数，则将所有数据 加上 min 的绝对值，使其变为非负数if (min < 0) {for (int i = 0; i < arrays.length; i++) {arrays[i] -= min;}max -= min;}// 定义二维数组，用于表示 桶，存储数据，bucket[0] ~ bucket[9] 分别用于存储 0 ~ 9 的数据int[][] bucket = new int[10][arrays.length];// 定义一维数组，用于表示 每个桶存储 数据的个数，bucketCount[0] ~ bucketCount[9] 分别用于存储 bucket[0] ~ bucket[9] 中数据的个数int[] bucketCount = new int[10];// 获取当前 最大值 的位数，根据 位数 确定需要进行 几次 数据划分操作int maxLength = (max + "").length();// 根据位数，按照 个位、十位、百位、千位 的顺序进行划分for (int i = 0, m = 1; i < maxLength; i++, m *= 10) {// 遍历数组，将数据划分到 桶中存储for (int j = 0; j < arrays.length; j++) {int temp = arrays[j] / m % 10; // 获取 个位、十位、百位 的值bucket[temp][bucketCount[temp]++] = arrays[j]; // 桶存储数据，相应的 bucketCount 也要加 1}int index = 0; // 用于记录新数组最后一个值的索引// 遍历桶，取出数据组成新的数组, k < bucketCount.length 或者 k < bucket[0].length 均可，都表示 10（0 ~ 9）for (int k = 0; k < bucketCount.length; k++) {// 当前桶存在数据时，取出数据存入数组中，并将该桶置空// 此处只需将 bucketCount 相应位置置 0 即可（无需将 bucket 置空，每次存储数据时均会覆盖，尽管会存在无用值，但无影响）if (bucketCount[k] > 0) {// 将桶元素复制到新数组中// 源数组 bucket[k]， 开始位置 0， 目标数组 arrays，目标数组起始位置 index，复制源数组的数据个数 bucketCount[k]System.arraycopy(bucket[k],0, arrays, index, bucketCount[k]);index += bucketCount[k];// 当前桶记录清空bucketCount[k] = 0;}}System.out.println("第 " + (i + 1) + " 次划分结果： " + Arrays.toString(arrays));}// 如果存在负数，则需要减去 相应的值if (min < 0) {for (int i = 0; i < arrays.length; i++) {arrays[i] += min;}}System.out.println("最终排序结果为： " + Arrays.toString(arrays));}
}【输出结果：】
第 1 次划分结果： [13, 65, 76, 97, 27, 38, 49]
第 2 次划分结果： [13, 27, 38, 49, 65, 76, 97]
最终排序结果为： [13, 27, 38, 49, 65, 76, 97]
====================
第 1 次划分结果： [10, 0, 23, 75, 37, 48, 9]
第 2 次划分结果： [0, 9, 10, 23, 37, 48, 75]
最终排序结果为： [-10, -1, 0, 13, 27, 38, 65]（3）分析：
若数据中出现相同的值，且向桶存放数据以及从桶取数据的过程中不会出现交换值的情况，故排序是稳定的。
每次均会遍历数据 n，且最大位数为 k，即 时间复杂度为 O(n*k)。
需要使用二维数组存储 桶元素，使用一维数组存储 桶存储元素个数，即空间复杂度为 O(10 * n + 10)，即空间复杂度为 O(n)。