10. 基数排序

[giscus[bot]]

10. 基数排序 | 算法通关手册

10. 基数排序 # 1. 基数排序算法思想 # 基数排序（Radix Sort）基本思想： 将整数按位数切割成不同的数字，然后按每个位数分别比较进行排序。 2. 基数排

https://algo.itcharge.cn/01.Array/02.Array-Sort/10.Array-Radix-Sort/

[shuaibird]

这个算法并没有考虑到负数

[wuxin0011]

还是记住这几个常用的吧

• 归并排序 O(nlogn）最稳定，大部分排序api都是基于这个，虽然小数据量时候使用的是快排（Java中是64）
• 计数排序 O(n)常用,在算法能够使用到类似思想,

[wuxin0011]

在Java中这些数据量的对应排序

    /**
     * The maximum number of runs in merge sort.
     */
    private static final int MAX_RUN_COUNT = 67;

    /**
     * The maximum length of run in merge sort.
     */
    private static final int MAX_RUN_LENGTH = 33;

    /**
     * If the length of an array to be sorted is less than this
     * constant, Quicksort is used in preference to merge sort.
     */
    private static final int QUICKSORT_THRESHOLD = 286;

    /**
     * If the length of an array to be sorted is less than this
     * constant, insertion sort is used in preference to Quicksort.
     */
    private static final int INSERTION_SORT_THRESHOLD = 47;

    /**
     * If the length of a byte array to be sorted is greater than this
     * constant, counting sort is used in preference to insertion sort.
     */
    private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29;

    /**
     * If the length of a short or char array to be sorted is greater
     * than this constant, counting sort is used in preference to Quicksort.
     */
    private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200;

python 中找不到源码好难受😭，不过应该大差不差

[wuxin0011]

计数排序其实和桶排序差不多，不过桶排序是节省了空间，计数排序中每个数据位置也可以看做一个桶，不过计数排序不能排序小数

[cattytyty]

这空间复杂度不是很懂