基数排序

[Ir1d]

https://oi-wiki.org/basic/radix-sort/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[Fomalhauthmj]

** for (int i = 1; i <= n; ++i) b[cnt[a[i].key[p]]--] = a[i];**
这句的循环是否有误，应为逆序？

[ehds]

@Fomalhauthmj
** for (int i = 1; i <= n; ++i) b[cnt[a[i].key[p]]--] = a[i];**
这句的循环是否有误，应为逆序？

应该是逆序。

[sbofgayschool]

@ehds

@Fomalhauthmj
** for (int i = 1; i <= n; ++i) b[cnt[a[i].key[p]]--] = a[i];**
这句的循环是否有误，应为逆序？

应该是逆序。

已修复～

[J-Corleone]

使用 “桶排序实现的桶排序” 和 ”桶排序后的桶内使用桶排序“ 一样吗？
有个思考题 能否用桶排序在O(n)内找出最小间隙，找不到相关的文章

[OhGaGaGaGa]

MSD 基数排序需要借助一种 稳定算法 完成内层对关键字的排序

MSD 中为何需要稳定算法？不稳定的算法应该也可以达到同样效果？

[OhGaGaGaGa]

Update: "不稳定的算法应该也可以达到同样效果？"，应修改为“不稳定的算法也可以实现不稳定的排序”

[arielherself]

引用原文：

一般而言，我们默认基数排序是稳定的，所以在 MSD 基数排序中，我们也仅仅考虑借助 稳定算法（通常使用计数排序）完成内层对关键字的排序。

[arielherself]

讲得好，一下就明白MSD和LSD的区别了

[zhangjialin996]

基于java的LSD排序：

package com.jialin.luogu;

import java.util.*;

public class  Main {
    public static void main(String... args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] arr = new int[N];
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < N; i++){
            arr[i] = in.nextInt();
            max = Math.max(max, arr[i]);
        }
        int length = 0;
        while(max != 0){
            length++;
            max = max / 10;
        }
        LSDSort(arr, length);
        for(int element : arr){
            System.out.print(element + " ");
        }
    }

    // 根据每一位进行桶计数排序
    public static void countingSort(int[] arr, int pos){
        int[] bucket = new int[10];
        for(int element : arr){
            bucket[getNumberInPos(element, pos)]++;
        }
        // prefix sum
        for(int i = 1; i < 10; i++) bucket[i] += bucket[i-1];
        int[] res = new int[arr.length];
        // 桶内顺序不变
        for (int i = arr.length - 1; i >= 0; i--) {
            res[--bucket[getNumberInPos(arr[i], pos)]] = arr[i];
        }
        System.arraycopy(res,  0, arr, 0, arr.length);
    }

    public static void LSDSort(int[] arr, int maxLength){
        int length = maxLength;
        while(maxLength > 0){
            maxLength--;
            countingSort(arr, length - maxLength);
        }
    }

    // get i pos num in a num
    public static int getNumberInPos(int num, int pos){
        int res;
        num = num / (int) Math.pow(10, (pos - 1));
        res = num % 10;
        return res;
    }
}

/*
example：
10
1 9 9 8 6 5 3 2 10 3
 */