桶排序

计数排序

计数排序（Counting Sort）是一种非比较型的排序算法，适用于对整数或有限范围内的数据进行排序。它的核心思想是通过统计每个元素的出现次数，然后根据统计结果将元素放回正确的位置。计数排序的时间复杂度为 $O(n + k)$，其中 n 是待排序元素的数量，k 是数据的范围大小。

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

根据一定的规律开辟一个合适的空间，如年龄按0-150的数组、一定范围的数组0-30的一个数组用来排一组数都是0-30范围的数等

桶排序

基数排序

桶排序是不基于比较的排序，它通过位上的关系来完成排序的。

它通过逐位比较元素的每一位（从最低位到最高位）来实现排序。基数排序的核心思想是将整数按位数切割成不同的数字，然后按每个位数分别进行排序。

1. 首先准备一个从 0 - 9 的桶，从左到右遍历数组，将该数放到该位上的数对应的桶里
2. 准备一个数组与排序数组一样大，从左到右遍历桶，每个桶里的数字先入先出（目的是保留历史排好的顺序）逐个放到备用数组里
3. 将备用数组拷贝回排序数组，周而复始直达最高位遍历完成

基数排序的时间复杂度为 $O(n * k)$ ，其中 n 是列表长度，k 是最大数字的位数。

package learn.note.algorithm.sort.three;

import java.util.Arrays;

/**
 * 基数排序
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] list = new int[] {5,2,1,6,7,1,6,87,12,5,2,6,89,100};
        radixSort(list);
        Arrays.stream(list).forEach(System.out::println);
        // 对数器
        CompareMachineUtil.compare(RadixSort::radixSort, null);
    }

    private static void radixSort(int[] list) {
        if (list == null || list.length < 2) {
            return;
        }
        // 获取最大值的尾数
        int maxBit = getMaxBit(list);

        // 需要循环的总次数
        for (int i = 1; i <= maxBit; i++) {
            // 0-9的桶
            int[] bucket = new int[] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
            // 从左往右进桶
            for (int i1 = 0; i1 < list.length; i1++) {
                // 取 i 位置上的数字
                int index = (list[i1] / ((int)Math.pow(10, i - 1))) % 10;
                bucket[index]++;
            }
            // 逐个求和
            for (int i2 = 1; i2 < bucket.length; i2++) {
                bucket[i2] = bucket[i2] + bucket[i2-1];
            }

            // 倒序
            int[] count = new int[list.length];
            for (int i3 = list.length - 1 ; i3 >= 0 ; i3--) {
                int index = (list[i3] / ((int) Math.pow(10, i - 1))) % 10;
                int countInd = bucket[index]--;
                count[countInd - 1] = list[i3];
            }

            // 拷贝回数组给下次循环做准备
            for (int i4 = 0; i4 < list.length ; i4++) {
                list[i4] = count[i4];
            }
        }
    }

    /**
     * 获取最大数的位的个数
     * @param list 数组
     * @return 获取最大数的位的个数
     */
    private static int getMaxBit(int[] list) {
        int max = Integer.MIN_VALUE;
        for (int item : list) {
            max = Math.max(max, item);
        }

        int maxBit = 0;
        while (max != 0) {
            maxBit++;
            max /= 10;
        }
        return maxBit;
    }
}