再谈基数排序-分治思想:对比计数|基数|桶|堆|希尔|快速|归并

基数排序，最先开始以为很复杂，其实就是正对正整数，先按照个位数大小对数组进行排序，再百位、千位、万位……

基数排序概述

基数排序 (Radix Sort) 其原理是将整数按位数切割成不同的数字，然后对每个位数上的数字进行分别比较。

这种排序算法可以可以追溯到1887年赫尔曼·霍勒里斯在制表机上的工作，它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

基数排序是一种非比较的整数排序算法，属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序。

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，都属于非比较排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr[i]之前有多少个元素，则唯一确定了arr[i]在排序后数组中的位置。

但对桶的使用方法上有明显差异：

• 计数排序：每个桶只存储单一键值；需要占用大量空间，它仅适用于数据比较集中的情况。比如 [0~100]，[10000~19999] 这样的数据。
• 桶排序：每个桶存储一定范围的数值；可用于最大最小值相差较大的数据情况，比如[9012,19702,39867,68957,83556,102456]。 但桶排序要求数据的分布必须均匀，否则可能导致数据都集中到一个桶中。比如[104,150,123,132,20000], 这种数据会导致前4个数都集中到同一个桶中。导致桶排序失效。
• 基数排序：根据键值的每位数字来分配桶；一般用于长度相同的元素组成的数组。基数排序可以看做是进行多趟桶排序。每个有效数字都在0-9之间，很适合桶排序，建10个桶很方便

这里个人总结下(对于整数排序)：

• 计数排序桶的个数N就是数组的 max-min+1，然后把数组的每一项数字num放到 num-min的桶中，然后按桶序依次取数
• 桶排序的桶的个数N是特定的，然后把数组的每一项数字num放到 num/[(max-min+1)/N]的桶中并对桶中数据排序，然后按桶序依次取数
• 基数排序，比如三位以内的数组，那么，就 个位、十位、百位分组（逻辑桶），然后先百位对数据排序、再十位、个位(这一步可以反着来：个位、十位、百位

对比排序

• 快速排序，如同用天平找出球堆中最重或最轻的球，数组分成3部分。一个基准值，一部分是小于基准值，一部分是大于基准值。把小于基准值的放在左边，大于基准值的放在右边。
• 归并排序，对半分数组，排序，将已有序的子序列合并。即：对n个元素进行排序。分解为先对n/2，在对n/2个元素排序，最后合并的问题。利用的是分治思想，还有递归的思想 。采用先分后合并的思想。
• 希尔排序，希尔排序又叫做缩小增量排序，按照增量gap一次取出N组数据，对对每组数据进行排序，然后按照组序合并数据，重复按照增加H-1重复上次操作，直至H=1，一般H等于数组长度的一半（基于二分的思想，但是很多情况表明二分不是最好的方法）有的是基与gap=gap/3+1来做的，还有研究表明，使用素数效率更高。当然，原理都是一样的。
• 堆排序，其实就是二叉树。

快速排序图解

归并排序图解

希尔排序图解

再次回到话题本身，基数排序

基数排序数组案列

通过基数排序对数组{53, 3, 542, 748, 14, 214, 154, 63, 616}，它的示意图如下：

基数排序分析

基数排序是将一个数分成几个部分，分别从后往前将每部分排序，其他部分作为卫星数据连带进行排序。

对于整数而言，因为每一位的大小都是0～9，因此可以对每一次使用计数排序，从而对任意整数进行排序。

假设需要排序的数位数d，因此如果对每一位都使用计数排序的话，总的时间复杂度为o(dn)

时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

例如，我们要把52张四种花色的扑克牌进行依次从小到大的排序，其中黑桃<红桃<方片<梅花。

这个问题的话，关键字为0~K和花色，而且花色的优先级大于数字，所以我们要先选择数字0~K先做一次排序，也就是分13个桶，分为标记为0~K，这样每个桶内就存在不同的四张花色的牌，这样我们收集起来了，然后我们再分4个桶，标记为不同的花色，然后把13个标记为数字的桶中的扑克牌依次放进这些桶内，最终我们可以不通过比较数字的大小和花色，就可以得到排序的结果了。

基数排序算法解析：

1. 基数排序的思想就是先排好各位，然后排好各位的基础上排十位，以此类推，直到遍历最高位 次，排序结束
2. 基数排序不是比较排序，而是通过分配和收集的过程来实现排序
3. 初始化10个桶(固定的)，桶下标为0-9
4. 通过得到待排序数字的个十百等位的数字，把这个数字对应的item放到对应的桶中

基数排序动画gif动画演示

基数排序有两种排序方式：LSD和MSD，最小位优先(从右边开始)和最大位优先(从左边开始)

最高有效位(MSD) 与最低有效位(LSD) 

• LSD (Least sgnificant digital)基数排序通常使用以下排序顺序：短键排在长键之前，相同长度的键按词法lexicographically 排序。这与整数表示的正常顺序是一致的，例如序列1、2、3、4、5、6、7、8、9、10、11。
• MSD (Most sgnificant digital)基数排序则使用词典顺序，它适用于对字符串(如单词) 或固定长度的整数进行排序。一个序列，如“b, c, d, e, f, g, h, i, j, ba”将会按词法排序为“b, ba, c, d, e, f, g, h, i, j”。如果词典排序用于表示可变量长度的整数，例如从1到10 的数字，输出将表示为1, 10, 2, 3, 4, 5, 6, 7, 8, 9。

LSD 的排序方式由键值的最右边开始，而 MSD 则相反，由键值的最左边开始。

基数排序JavaScript实现代码

基数排序JavaScript 算术实现起来，代码非常简洁

/**
 * 基数排序，正整数
 * @param arr {[Number]} 待排序数组
 * @param precision {Number} 数组最大数字位数
 */
function radixSort (arr, precision) {
    for (let i = 0; i < precision + 1; i++) {
        // 分个、十、百、千……位，针对每个位数的数字大小，对数组进行排序。个位除1，十位除10，百位除100……
        let buckets = []
        let digit = Math.pow(10, i)
        for (let i = 0; i < arr.length; i++) {
            let index = Math.floor(arr[i] / digit)
            if (buckets[index] === undefined) {
                buckets[index] = [arr[i]]
            } else {
                buckets[index].push(arr[i])
            }
        }
        arr = [].concat(...buckets)
    }
    return arr
}

针对负数的，待续……

参考文章：

转载自：cococo点点 http://www.cnblogs.com/coder2012

排序之计数排序，基数排序和桶排序 https://www.cnblogs.com/jiangfan95/p/11498625.html

【排序算法（七）】基数排序 https://blog.csdn.net/qq_41900081/article/details/86831408

基数排序 radix sort https://www.jianshu.com/p/8340dfaea3af

转载本站文章《再谈基数排序-分治思想:对比计数|基数|桶|堆|希尔|快速|归并》, 请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/SortingAlgorithms/8279.html