姬長信(Redy)

十大排序算法之基数排序

本文首发于[个人博客](https://ityongzhen.github.io/十大排序算法之基数排序.html) ## 前言 本系列排序包括十大经典排序算法。 ![](https://user-gold-cdn.xitu.io/2019/10/31/16e20f98f291723e?imageView2/0/w/1280/h/960/format/webp/ignore-error/1) - 使用的语言为/uff1aJava - 结构为/uff1a 定义抽象类`Sort`里面实现了/uff0c交换/uff0c大小比较等方法。例如交换两个值/uff0c直接传入下标就可以了。其他的具体排序的类都继承抽象类`Sort`。这样我们就能专注于算法本身。 ~~~~ /* * 返回值等于0/uff0c代表 array[i1] == array[i2] * 返回值小于0/uff0c代表 array[i1] array[i2] */ protected int cmp(int i1, int i2) { return array[i1].compareTo(array[i2]); } protected int cmp(T v1, T v2) { return v1.compareTo(v2); } protected void swap(int i1, int i2) { T tmp = array[i1]; array[i1] = array[i2]; array[i2] = tmp; } ~~~~ - 冒泡、选择、插入、归并、希尔、堆排序都是基于比较的排序 - 平均时间复杂度最低O(nlogn) - 计数排序、桶排序、基数排序不是基于比较的排序 - 使用空间换时间/uff0c某些时候/uff0c平均时间复杂度可以低于O(nlogn) ## 什么是基数排序 - [基数排序](https://baike.baidu.com/item/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F)/uff08radix sort/uff09属于/u201c分配式排序/u201d/uff08distribution sort/uff09/uff0c又称/u201c桶子法/u201d/uff08bucket sort/uff09或bin sort/uff0c顾名思义/uff0c它是透过键值的部份资讯/uff0c将要排序的元素分配至某些/u201c桶/u201d中/uff0c藉以达到排序的作用/uff0c基数排序法是属于稳定性的排序/uff0c其时间复杂度为O (nlog(r)m)/uff0c其中r为所采取的基数/uff0c而m为堆数/uff0c在某些时候/uff0c基数排序法的效率高于其它的稳定性排序法 ### 实现方法 - 最高位优先(Most Significant Digit first)法/uff0c简称MSD法/uff1a先按k1排序分组/uff0c同一组中记录/uff0c关键码k1相等/uff0c再对各组按k2排序分成子组/uff0c之后/uff0c对后面的关键码继续这样的排序分组/uff0c直到按最次位关键码kd对各子组排序后。再将各组连接起来/uff0c便得到一个有序序列。 - 最低位优先(Least Significant Digit first)法/uff0c简称LSD法/uff1a先从kd开始排序/uff0c再对kd-1进行排序/uff0c依次重复/uff0c直到对k1排序后便得到一个有序序列。 ## 算法思想 ### 第一步 以LSD为例/uff0c假设原来有一串数值如下所示/uff1a >73, 22, 93, 43, 55, 14, 28, 65, 39, 81 首先根据个位数的数值/uff0c在走访数值时将它们分配至编号0到9的桶子中/uff1a ~~~~ 0 1 81 2 22 3 73 93 43 4 14 5 55 65 6 7 8 28 9 39 ~~~~ ### 第二步 接下来将这些桶子中的数值重新串接起来/uff0c成为以下的数列/uff1a >81, 22, 73, 93, 43, 14, 55, 65, 28, 39 接着再进行一次分配/uff0c这次是根据十位数来分配/uff1a ~~~~ 0 1 14 2 22 28 3 39 4 43 5 55 6 65 7 73 8 81 9 93 ~~~~ ### 第三步 接下来将这些桶子中的数值重新串接起来/uff0c成为以下的数列/uff1a >14, 22, 28, 39, 43, 55, 65, 73, 81, 93 这时候整个数列已经排序完毕/uff1b如果排序的对象有三位数以上/uff0c则持续进行以上的动作直至最高位数为止。 - LSD的基数排序适用于位数小的数列/uff0c如果位数多的话/uff0c使用MSD的效率会比较好。MSD的方式与LSD相反/uff0c是由高位数为基底开始进行分配/uff0c但在分配之后并不马上合并回一个数组中/uff0c而是在每个/u201c桶子/u201d中建立/u201c子桶/u201d/uff0c将每个桶子中的数值按照下一数位的值分配到/u201c子桶/u201d中。在进行完最低位数的分配后再合并回单一的数组中。 ## 算法稳定性 - 基数排序是一种稳定排序算法。 ### 是否是原地算法 - 何为原地算法/uff1f - 不依赖额外的资源或者依赖少数的额外资源/uff0c仅依靠输出来覆盖输入 - 空间复杂度为 /ud835/udc42(1) 的都可以认为是原地算法 - 非原地算法/uff0c称为 Not-in-place 或者 Out-of-place - 基数排序不属于 In-place ### 时空复杂度 - 最好、最坏、平均时间复杂度/uff1aO(d*(n+k)) - d是最大值的位数/uff0ck是进制 - 空间复杂度/uff1aO(n+k) ## 代码 - [十大排序算法之计数排序](https://ityongzhen.github.io/十大排序算法之计数排序.html)中/uff0c先使用最简单的实现方案/uff0c先求最大值/uff0c用于创建数组/uff0c然后遍历出来/uff0c统计元素出现的次数/uff0c最后再按照顺序赋值 - 基数排序内部的实现可以用计数排序的思路 ~~~~ package YZ.Sort; public class RadixSort extends Sort { @Override protected void sort() { int max = array[0]; for (int i = 1; i max) { max = array[i]; } } // 个位数: array[i] / 1 % 10 = 3 // 十位数/uff1aarray[i] / 10 % 10 = 9 // 百位数/uff1aarray[i] / 100 % 10 = 5 // 千位数/uff1aarray[i] / 1000 % 10 = ... for (int divider = 1; divider =0 ; i--) { //获取元素在counts中的索引 int index = array[i]/divider; //获取元素在counts中的值 //counts[index]; //放在合适位置 newArray[--counts[index]] = array[i]; } // 将有序数组赋值到array for (int i = 0; i Integer[] array = Integers.random(20000, 1, 80000); > ### 结果如下 【CountingSort】 稳定性/uff1atrue 耗时/uff1a0.005s(5ms) 比较次数/uff1a0 交换次数/uff1a0 【QuickSort】 稳定性/uff1afalse 耗时/uff1a0.009s(9ms) 比较次数/uff1a33.27万 交换次数/uff1a1.32万 【MergeSort】 稳定性/uff1atrue 耗时/uff1a0.01s(10ms) 比较次数/uff1a26.10万 交换次数/uff1a0 【RadixSort】 稳定性/uff1atrue 耗时/uff1a0.014s(14ms) 比较次数/uff1a0 交换次数/uff1a0 【ShellSort】 稳定性/uff1afalse 耗时/uff1a0.016s(16ms) 比较次数/uff1a43.34万 交换次数/uff1a0 【HeapSort】 稳定性/uff1afalse 耗时/uff1a0.023s(23ms) 比较次数/uff1a51.09万 交换次数/uff1a2.00万 【SelectionSort】 稳定性/uff1atrue 耗时/uff1a0.514s(514ms) 比较次数/uff1a2.00亿 交换次数/uff1a2.00万 【InsertionSort1】 稳定性/uff1atrue 耗时/uff1a1.362s(1362ms) 比较次数/uff1a9935.15万 交换次数/uff1a9933.15万 【BubbleSort】 稳定性/uff1atrue 耗时/uff1a2.529s(2529ms) 比较次数/uff1a2.00亿 交换次数/uff1a9933.15万 ## 代码地址/uff1a - 文中的代码在git上/uff1a[github地址](https://github.com/ITyongzhen/DataStructureAndAlgorithm)