基数排序（详细图解）

一、什么是基数排序

（1）通过键值得各个位的值，将要排序的元素分配至一些桶中，达到排序的作用
（2）基数排序法是属于稳定性的排序，基数排序法是效率高的稳定排序法
（3）基数排序是桶排序的扩展

二、实现原理

        将所有待比较数值（自然数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

三、实现步骤

（1）确定数组中的最大元素有几位（MAX）（确定执行的轮数）

（2）创建0~9个桶（桶的底层是队列），因为所有的数字元素都是由0~9的十个数字组成

（3）依次判断每个元素的个位，十位至MAX位，存入对应的桶中，出队，存入原数组；直

         至MAX轮结束输出数组。

（4）具体实现步骤如下图

四、代码实现

import java.util.LinkedList;

public class Radix {

	public static void main(String[] args) {

		int[] arr = { 23, 1, 4, 9, 98, 132, 42 };

		sort(arr);

	}

	public static void sort(int[] arr) {
		// 1.找 分类-收集 的轮数（最大值的长度）
		int radix = getRadix(arr);
		// 2.创建桶 list所有桶的集合 每一个桶是LinkedList当成队列来用
		LinkedList<Integer>[] list = new LinkedList[10];
		for (int i = 0; i < list.length; i++) {
			list[i] = new LinkedList<>();
		}
		// 3.开始 分类-收集
		for (int r = 1; r <= radix; r++) {
			// 分类过程
			for (int i = 0; i < arr.length; i++) {
				list[getIndex(arr[i], r)].offer(arr[i]);
			}
			int index = 0; // 遍历arr原数组
			// 收集的过程
			for (int i = 0; i < list.length; i++) {
				while (!list[i].isEmpty()) {
					arr[index++] = list[i].poll();
				}
			}

		}

		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + "  ");
		}

	}

	private static int getIndex(int num, int r) {
		int ret = 0;
		for (int i = 1; i <= r; i++) {
			ret = num % 10;
			num /= 10;
		}
		return ret;
	}

	private static int getRadix(int[] arr) {
		int max = arr[0];
		for (int i = 1; i < arr.length; i++) {
			if (arr[i] > max) {
				max = arr[i];
			}
		}
		return (max + "").length();
	}

}