随笔记录

算法-基数排序

2022-4-2 diaba 算法

package com.jiucaiyuan.net.algrithm.sort;

import java.net.InetSocketAddress;

/**
 * <pre>
 * 基数排序
 *  根据数据特点进行排序，而非基于比较
 * 	 时间复杂度O(N*logN)  空间复杂度O(1)
 * </pre>
 * Created by jiucaiyuan on 2022/4/1.
 */
public class RadixSort {
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        radixSort(arr, 0, arr.length - 1, maxBits(arr));
    }

    /**
     * 找出数组中最大数字的宽度
     *
     * @param arr
     * @return
     */
    public static int maxBits(int[] arr) {
        int max = Integer.MIN_VALUE;
        //找到最大的数
        for (int i : arr) {
            max = Math.max(i, max);
        }
        //计算宽度
        int result = 0;
        while (max != 0) {
            result++;
            max /= 10;
        }
        return result;
    }

    /**
     * 针对arr[l~r]进行排序
     *
     * @param arr   待排序数组
     * @param l     左侧下标
     * @param r     右侧下标
     * @param digit l到r之间最大数字的字符数（宽度）
     */
    public static void radixSort(int[] arr, int l, int r, int digit) {
        final int radix = 10;
        int i = 0, j = 0;
        //有多少个数据，就准备多少个辅助空间
        int[] bucket = new int[r - l + 1];
        //有多少位，就进出几次桶
        for (int d = 1; d <= digit; d++) {
            //10个空间
            //count[0],当前位置（d位）是0的数字有多少个
            //count[1],当前位置（d位）是0和1的数字有多少个
            //count[2],当前位置（d位）是0、1和2的数字有多少个
            //count[3],当前位置（d位）是0、1、2和3的数字有多少个
            //  ...
            //count[i],当前位置（d位）是0~i的数字有多少个
            //count[0~9]
            int[] count = new int[radix];
            //累计d位置出现j的次数
            for (i = l; i <= r; i++) {
                j = getDigit(arr[i], d);
                count[j]++;
            }
            //count数组转化为count[i]为所有<=i的数字之和，即小于等于i的个数之和
            //把count处理成前缀和
            for (i = 1; i < radix; i++) {
                count[i] = count[i - 1] + count[i];
            }
            //把i位置上的数，放到d位置上的数字及之前出现的次数-1的辅助空间中
            //等于操作了入桶和出桶操作
            for (i = r; i >= l; i--) {
                j = getDigit(arr[i], d);
                bucket[--count[j]] = arr[i];
            }
            //局部处理完的数组拷贝回原数组
            for (i = l, j = 0; i <= r; i++, j++) {
                arr[i] = bucket[j];
            }
            print(bucket);
        }
    }

    /**
     * 返回数字num倒数第d位置的数字
     * @param num
     * @param d
     * @return
     */
    private static int getDigit(int num, int d) {
        return (num / ((int) Math.pow(10, d - 1))) % 10;
    }

    public static void main(String[] args) {
        int[] arr = {12, 15, 63, 102, 32, 53, 908};
        radixSort(arr);
        System.out.println("-------------");
        print(arr);
    }

    private static void print(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int a : arr) {
            System.out.print(a + "\t");
        }
        System.out.println();
    }
}