我的《恋上数据结构》源码（第1季 + 第2季）：https://github.com/szluyu99/Data_Structure_Note

经典的十大排序算法！

前言

请==务必==看一下这个：排序算法前置知识+代码环境准备。

当上面的内容都准备好以后，那就开始基数排序吧！

基数排序

基数排序非常适合用于整数排序（尤其是非负整数），这里只介绍对非负整数进行基数排序。

执行流程：依次对个位数、十位数、百位数、千位数、万位数...进行排序（从低位到高位）

代码实现

个位数、十位数、百位数的取值范围都是固定的0~9，可以使用计数排序对它们进行排序。

package com.mj.sort;

public class RadixSort extends Sort<Integer> {

    @Override
    protected void sort() {
        // 找出最大值
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        
        // 个位数: array[i] / 1 % 10 = 3
        // 十位数：array[i] / 10 % 10 = 9
        // 百位数：array[i] / 100 % 10 = 5
        // 千位数：array[i] / 1000 % 10 = ...

        for (int divider = 1; divider <= max; divider *= 10) {
            countingSort(divider);
        }
    }
    
    protected void countingSort(int divider) {
        // 开辟内存空间，存储次数
        int[] counts = new int[10];
        // 统计每个整数出现的次数
        for (int i = 0; i < array.length; i++) {
            counts[array[i] / divider % 10]++;
        }
        // 累加次数
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }
        
        // 从后往前遍历元素，将它放到有序数组中的合适位置
        int[] newArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            newArray[--counts[array[i] / divider % 10]] = array[i];
        }
        
        // 将有序数组赋值到array
        for (int i = 0; i < newArray.length; i++) {
            array[i] = newArray[i];
        }
    }
}

复杂度与稳定性

• 最好、最坏、平均时间复杂度：O(d ∗ (n + k)) ，d 是最大值的位数，k 是进制
• 空间复杂度：O(n + k)，k 是进制
• 基数排序属于稳定排序

基数排序-另一种思路

代码实现

复杂度与稳定性

• 空间复杂度是 O(kn + k) ，时间复杂度是 O(dn)
• d 是最大值的位数，k 是进制

桶排序

执行流程：

• ① 创建一定数量的桶（比如用数组、链表作为桶）
• ② 按照一定的规则（不同类型的数据，规则不同），将序列中的元素均匀分配到对应的桶
• ③ 分别对每个桶进行单独排序
• ④ 将所有非空桶的元素合并成有序序列

元素在桶中的索引：元素值 * 元素数量

实现

复杂度与稳定性

• 空间复杂度：O(n + m)，m 是桶的数量
• 时间复杂度：

因此为 O(n + k)，k 为 n ∗ logn − n ∗ logm

• 桶排序属于稳定排序

"最强排序"-休眠排序

/**
 * 休眠排序
 */
public class SortThread extends Thread{
    public int value;
    public SortThread(int value) {
        this.value = value;
    }
    public void run(){
        try{
            Thread.sleep(value);
            System.out.println(value);
        }catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    public static void main(String[] args) {
        int [] array = {10, 100, 50, 30, 60, 61, 64, 47,79, 59};
        for (int i = 0; i < array.length; i++) {
            new SortThread(array[i]).start();
        }
        
    }
}