【排序算法】- 基数排序_综合

排序动图

排序思路

将数组按基数进行排序，个位，十位，百位…

排序流程

取数组中最大的数，并计算位数
从最低位开始取每个位的数组成一个新的数组
对新的数组重新按位排序，直到位数排完

代码实现

public static void radixSort(int[] arr) {
    // 找出最大的数int max = Integer.MIN_VALUE;for (int i = 0; i < arr.length; i ++) {
    if (arr[i] > max) {
    max = arr[i];}}// 计算最大的数有几位int length = (max+"").length();// 存放每次排序后的数字int[] temp = arr;// temp 数组的下标int index = 0;// 排序 length 次 n 代表每次的需要取模的值for (int i = 0, n = 1; i < length; i++, n*=10) {
    // 存放每个位置对应的数int[][] bucket = new int[10][arr.length];// 存放每个下标放了一个数字int[] counts = new int[10];// 排序for (int j = 0; j < arr.length; j++) {
    // 取模放入对应的数组中int indexVal = temp[j] / n % 10;bucket[indexVal][counts[indexVal]] = temp[j];counts[indexVal] = ++counts[indexVal];}// 将每个下标的数字按顺序取出来for (int k = 0; k < 10; k++) {
    for (int l = 0; l < counts[k]; l++) {
    temp[index] = bucket[k][l];index++;}}// index 归 0index = 0;}// 将临时数组赋予真实数组for (int i = 0; i < arr.length; i++) {
    arr[i] = temp[i];}
}

代码优化 - 使用队列记录数组

自定义队列 MyQueue.java

public class MyQueue {
    /*** 使用数组作为队列的底层*/private int[] arr;/*** 构造方法*/public MyQueue() {
    arr = new int[0];}/*** 入队** @param e 入队的元素*/public void add(int e) {
    // 创建一个新的数组int[] newArray = new int[arr.length + 1];// 将数据复制到新数组for (int i = 0; i < arr.length; i++) {
    newArray[i] = arr[i];}// 入队newArray[arr.length] = e;// 将新数组赋值给原来的数组arr = newArray;}/*** 出队** @return 出队的元素*/public int poll() {
    // 队列是否为空if (isEmpty()) {
    throw new RuntimeException("Queue is Empty");}// 记录出队的元素int e = arr[0];// 创建一个新的数组int[] newArray = new int[arr.length-1];// 将数据复制到新数组for (int i = 0; i < newArray.length; i++) {
    newArray[i] = arr[i+1];}// 将新数组赋值给原来的数组arr = newArray;// 返回出队的元素return e;}/*** 队列是否为空** @return true/false*/public boolean isEmpty() {
    return arr.length == 0;}
}

使用队列优化技术排序 RadixQueueSort.java

public class RadixQueueSort {
    public static void main(String[] args) {
    int[] arr = new int[]{
    54, 4, 36, 125, 435, 52, 23, 678, 34, 12, 879};radixQueueSort(arr);System.out.println(Arrays.toString(arr));}/*** 使用队列实现基数排序** @param arr 数组*/public static void radixQueueSort(int[] arr) {
    // 定义最大值，找出最大的数int max = Integer.MIN_VALUE;for (int i = 0; i < arr.length; i++) {
    if (max < arr[i]) {
    max = arr[i];}}// 计算最大值的位数int length = (max + "").length();// 定义一个记录数字的队列数组 0 1 2 3 4 ...MyQueue[] myQueue = new MyQueue[10];// 为每个队列初始化for (int i = 0; i < myQueue.length; i++) {
    myQueue[i] = new MyQueue();}// 定义一个记录排序好的数组int[] temp = arr;// 记录临时数组的下标int index = 0;// 循环基数排序for (int i = 0, n = 1; i < length; i++, n *= 10) {
    // 遍历所有数据for (int j = 0; j < temp.length; j++) {
    // 计算余数int indexVal = temp[j] / n % 10;// 加入对应余数的队列myQueue[indexVal].add(temp[j]);}// 取出队列中的数据for (int k = 0; k < myQueue.length; k++) {
    while (!myQueue[k].isEmpty()) {
    temp[index] = myQueue[k].poll();index++;}}// 将 index 初始为 0index = 0;}// 将临时数组赋值给原来的数组for (int i = 0; i < arr.length; i++) {
    arr[i] = temp[i];}}
}