常用排序算法原理及实践

排序

1. 冒泡排序
2. 选择排序
3. 插入排序
4. 归并排序
5. 快速排序
6. 基数排序LSD
7. 练习：小和问题、荷兰国旗问题、找中位数、最大间距

排序算法	时间复杂度	空间复杂度	算法稳定性
冒泡排序	O(n^2)	O(1)	稳定
选择排序	O(n^2)	O(1)	不稳定
插入排序	O(n^2)	O(1)	稳定
归并排序	O(nlogn)	O(n)	稳定
快速排序	O(nlogn)	O(logn)	不稳定

稳定性分析

如果待排序的序列中存在两个或两个以上具有相同关键词的数据，排序后这些数据的相对次序保持不变，即它们的位置保持不变，

通俗地讲，就是两个相同的数的相对顺序不会发生改变，则该算法是稳定的；

如果排序后，数据的相对次序发生了变化，则该算法是不稳定的。

保证稳定性的意义：

• 真实业务中需要稳定性，即希望在排序过程中原始序列的信息不要被抹去。
• 如对象包含：名称name,年龄age,身高height
  • 先按身高height进行排序，得到有序队列；存在身高height不同，年龄age相同的对象；
  • 再按年龄age进行排序，如果排序算法是稳定的，将可以保存原始按身高height排序后的序列信息（年龄相同，身高不同的的对象，是按身高有序排列的）；

常用排序算法及稳定性：

• 稳定：
  • 冒泡排序 Bubble Sort （逐个之间比较，再交换）
  • 插入排序 Insertion sort （从待排序序列中依次取出，从已排序序列末尾开始，逐个比较，再交换）
  • 归并排序 Merge Sort (基于外部排序合并有序数组，依次对两个有序序列，逐个进行排列)
• 不稳定：
  • 选择排序 Selection sort （从整个待排序序列中选择最小，再与待排序序列的首位交换）
  • 快速排序 Quick Sort （从待排序序列中选定某个分界值，选择小于分界值的数，再与待排序数组左部分不小于分界值的序列的首位交换）

冒泡排序 Bubble Sort

实质：把小的元素往前调或者把大的元素往后调

时间复杂度： O(n^2)

空间复杂度： O(1)

算法稳定性： 稳定排序算法

原理：

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个(已经是本次冒泡中最大的元素)。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

for(int i = arr.length-1 ; i > 0 ; i--){
  for (int j = 0 ; j < i ; j++){
    if(arr[j] > arr[j+1]){
      swap(arr,j,j+1);
    }
  }
}

算法稳定性：

• 冒泡排序就是把小的元素往前调或者把大的元素往后调。
• 比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；
• 如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

选择排序 Selection sort

实质：遍历未排序序列，选择出最小的元素排列成有序序列

时间复杂度： O(n^2)

空间复杂度： O(1)

算法稳定性： 不稳定的排序方法

• [5 8 5 2] 找出最小的一个与第一个位置交换，稳定性被破坏。

原理：

• 首先，在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
• 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
• 以此类推，直到所有元素均排序完毕。

for (int i = 0 ; i < arr.length-1 ; i++){
    int minIndex = i;
    for (int j = i + 1 ; j < arr.length ; j++){
        if(arr[j] < arr[minIndex]){
            minIndex = j;
        }
    }
    swap(arr,i, minIndex);
}

算法稳定性：

• 选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。
• 那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。
• 举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法

插入排序 Insertion sort

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。

实质：将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表；直到整个序列排为有序的过程。

时间复杂度： O(n^2)

空间复杂度： O(1)

算法稳定性： 稳定的排序方法

原理：

• 在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，
• 现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。
• 按照此法对所有元素进行插入，直到整个序列排为有序的过程。

for (int i = 1 ; i < arr.length ; i++){
    for (int j = i ; j > 0 ; j--){
        if(arr[j] < arr[j-1]){
            swap(arr,j-1, j);
        }
    }
}

应用：

• 插入排序适用于已经有部分数据已经排好，并且排好的部分越大越好。
• 一般在输入规模大于1000的场合下不建议使用插入排序 。

时间复杂度分析：

• 最优的情况： 在插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较N- 1次，时间复杂度为：O(N)
• 最差的情况： 最坏的情况是待排序数组是逆序的，此时需要比较次数最多，总次数记为：1+2+3+…+N-1，所以，插入排序最坏情况下的时间复杂度为：O(N^2)
• 平均情况： 平均来说，A[1…j-1]中的一半元素小于A[j]，一半元素大于A[j]。插入排序在平均情况运行时间与最坏情况运行时间一样，时间复杂度为：O(N^2)

稳定性分析：

• 关键词相同的数据元素将保持原有位置不变，所以插入排序算法是稳定的

归并排序 Merge Sort

实质：采用分治法，将已有序的子序列合并，得到完全有序的序列；

时间复杂度： O(n * logn)

空间复杂度： O(n)

算法稳定性： 稳定的排序方法

• 先放左边，再放右边

原理：

• 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
• 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置；
• 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
• 重复步骤3直到某一指针超出序列尾；
• 将另一序列剩下的所有元素直接复制到合并序列尾；

private int[] mergeSort(int[] arr, int L, int R){
    if(L == R){
        return arr;
    }

    int mid = L + ( (R-L) >> 1 );
    mergeSort(arr, L , mid);
    mergeSort(arr,mid+1 , R);
    merge(arr, L, mid, R);

    return arr;
}

private void merge(int[] arr, int L, int mid, int R) {
    int[] newArr = new int[R-L+1];
    int a = L ;
    int b = mid + 1 ;
    int c = 0 ;
    while ( a <= mid && b <= R ){
        if(arr[a] > arr[b]){
            newArr[c++] = arr[b++];
        }else {
            newArr[c++] = arr[a++];
        }
    }
    while ( a <= mid){
        newArr[c++] = arr[a++];
    }
    while ( b <= R ){
        newArr[c++] = arr[b++];
    }

    for (int i = 0; i < newArr.length ; i++){
        arr[L+i] = newArr[i];
    }
}

Master公式：T(N) = a * T(N/b) + O(N^d)

• log(b,a) > d -> 复杂度为：O(N^log(b,a))
• log(b,a) = d -> 复杂度为：O(N^d * logN)
• log(b,a) < d -> 复杂度为：O(N^d)

T(N)：样本量为N的情况下的时间复杂度

a*T(N/b) : 子过程调用的时间复杂度

O(N^d) ：除掉子过程调用外，剩余操作的时间复杂度

时间复杂度分析：

• 时间复杂度：T(N) = 2 * T(N/2) + O(N)
• 2 * T(N/2) ，将样本量等分为两部分，每部分时间复杂度为：T(N/2)；只考虑样本量规模，不考虑常数项
• O(N) 使用外排的方式将两个有序数组合并的时间复杂度
• 套用Master公式得时间复杂度为：
  • a = 2, b = 2, d = 1
  • log(2,2) = 1， 复杂度公式为：O(N * logN)

应用：

• 速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

补充：

• 归并排序的额外空间复杂度可以变成O(1)， 但是非常难， 不需要掌握， 可以搜“归并排序 内部缓存法”

小和问题

牛客网-题库-在线编程-程序员代码面试指南-CD21-计算数组的小和

https://www.nowcoder.com/ta/programmer-code-interview-guide

题目描述：数组小和的定义如下：

• 例如，数组s = [1, 3, 5, 2, 4,6]，
• 在s[0]的左边小于或等于s[0]的数的和为0；
• 在s[1]的左边小于或等于s[1]的数的和为1；
• 在s[2]的左边小于或等于s[2]的数的和为1+3=4；
• 在s[3]的左边小于或等于s[3]的数的和为1；
• 在s[4]的左边小于或等于s[4]的数的和为1+3+2=6；
• 在s[5]的左边小于或等于s[5]的数的和为1+3+5+2+4=15。
• 所以s的小和为0+1+4+1+6+15=27
• 给定一个数组s，实现函数返回s的小和
• [要求] 时间复杂度为O(nlogn)O(nlogn)，空间复杂度为O(n)O(n)

解题思路：

• 利用归并排序，采用分治思想，等分为两部分，
• 对左边部分进和排序并计算左边部分的小和，
• 对右边部分进行排序并计算右边部分的小和，
• 利用外排对两个有序数组进行合并；合并过程中，当左边数组的元素arr[a]小于等于右边数组的元素arr[b]时，累加小和：因为右边数组是有序的，所以小和为右边数组剩余元素数量 * 元素值 ，mergeSum += (arr[a] * (R-b+1))。

参考代码：com.chen.algorithm.sort.SmallSum

问题一 数组分区

给定一个数组arr， 和一个数num， 请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。

要求：额外空间复杂度O(1)， 时间复杂度O(N)

解题思路：

• 使用变量X，代表从数组从0~X范围内的所有数都是小于等于num的，X初始为-1；
• 使用变量i遍历数组arr，当arr[i] <= num时，X++，交换arr[X]和arr[i]的值；
• 当遍历完成时，即可实现数组0~X的数都是小于等于num的。

参考代码：com.chen.algorithm.sort.PartitionArray

问题二 荷兰国旗问题

给定一个数组arr， 和一个数num， 请把小于num的数放在数组的左边， 等于num的数放在数组的中间， 大于num的数放在数组的右边。

要求：额外空间复杂度O(1)， 时间复杂度O(N)

解题思路：

• 使用变量L，代表从数组0 ~ L范围内的所有数都是小于num的，L初始值为-1;
• 使用变量R，代表从数组R ~ (arr.length-1)范围内所有数都是大于num的，R初始值为arr.length;
• 使用变量i遍历数组arr,当arr[i] < num时，X++，交换arr[X] 和 arr[i]的值，i++；
• 当arr[i] == num时，i++;
• 当arr[i] > num时，R–，交换arr[i] 和 arr[R]的值，i不变；
• 当i==R时，遍历完成；即可实现数组0 ~ X的数都是小于num的，R ~ (arr.length-1)的数都是大于num的，(L+1) ~ (R-1)的数都是等于num的。

参考代码：com.chen.algorithm.sort.NetherlandsFlag

快速排序 Quick Sort

实质： 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

时间复杂度： O(n * logn)

空间复杂度： O(logn)

算法稳定性： 不稳定的排序方法

原理：

• 快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
• (1) 首先设定一个分界值，通过该分界值将数组分成左右两部分。
• (2) 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
• (3) 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
• (4) 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
• 经典快速排序： 选取数组的最后一个元素作为分界值；缺点：划分的两部分规模可能是不均衡的，排序的性能受到样本情况影响，如：
  • 最差情况：数组是一个有序数组，每次取最后一个元素作为分界值，性能为最差情况，时间复杂度为O(n^2)；
  • 最优情况：每次选取的分界值，划分的两部分都是相等的，时间复杂度为O(n * logn)
• 随机快速排序： 随机选择数组中的某个元素作为分界值，时间复杂度性能转变为概率事件，时间复杂度长期期望为O(nlogn)
• 优化点： 参考荷兰国旗问题，可以改进划分规则，划分为三部分，将小于分界值的放左边，等于分界值的放中间，大于分界值的放右边；这样每一次快速排序就可以处理该区间内一批相等的数，而不是每一次快速排序只处理分界值这一个数。

算法避免受原始样本数据影响，常规操作：

• 随机
• 哈希

空间复杂度分析：

• 从空间性能上看，尽管快速排序只需要一个元素的辅助空间，但快速排序需要一个栈空间来实现递归。
• 最好的情况下，即快速排序的每一趟排序都将元素序列均匀地分割成长度相近的两个子表，所需栈的最大深度为log(n+1)；
• 但最坏的情况下，栈的最大深度为n。
• 因为分界值是随机获取，是一个概率事件，这样，长期期望，快速排序的空间复杂度为O(logn)。

应用：

• 随机快排是在工程中最常用的一种排序，工程中不会使用递归实现，而是会使用非递归实现。
• 实现简单，常数项低

补充：

• 快速排序可以做到稳定性问题， 但是非常难， 不需要掌握，可以搜“01 stable sort”；
• 类似题目： 是奇数放在数组左边，偶数放在数组右边，还要求原始的相对次序不变；时间复杂度O(n) 空间复杂度O(1)

参考代码：com.chen.algorithm.sort.QuickSort

堆排序 Heap Sort

实质：利用堆的数据结构特性实现排序

时间复杂度： O(n * logn)

空间复杂度： O(1)

算法稳定性： 不稳定的排序方法

• [4 4 4 5 5] 建立大根堆时稳定性就会破坏

完全二叉树：若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的节点数都达到最大个数，第k 层所有的结点都连续集中在最左边，这就是完全二叉树。

完全二叉树父子节点下标k的关系： 一个节点的下标为k，其左孩子节点的下标为2k+1，右孩子节点的下标为2k+2；一个节点的下标为k，其父节点的下标(k-1)/2

堆： 是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

原理：

• 利用大根堆的特性，
• 第一步： 将待排序的数组整理成大根堆（heapify）；依次将数组中的元素添加到堆的最后一个节点，为维护大根堆的特性，对每一个新添加的元素即堆的最后一个元素进行最大堆调整（Sift Up）；
• 第二步： 取出大根堆的根节点（extractMax），即最大值，与堆的最后一个元素交换，堆的大小减1，即完成待排序数组的最后一个元素的排序；
• 第三步： 对大根堆的根节点进行最大堆调整（Sift Down），维护大根堆的特性；
• 重复第二步的操作，直到堆中所有数据全部取出，完成数组排序。

堆中定义以下几种操作：

• 创建最大堆（heapify）： 将任意数组整理成大根堆；时间复杂度分析：逐个将元素添加到堆中，对每个元素执行上浮操作(Sift Up)，总共有N个，时间复杂度为(O(log1)+O(log2)+…+O(logn-1)) 结果收敛于 O(N)
• 上浮：对堆的最后一个节点进行最大堆调整(Sift Up)： 对堆的最后一个节点进行上浮操作（根据当前节点的下标k，得到父节点下标(k-1)/2，比较两个位置的数值，如果比父节点的大，交换两个位置的数，递归直到根节点或比父节点值小结束），使得堆维持大根堆的特性； O(logN)
• 取出堆中的最大元素（extractMax）： 取出大根堆的根节点 O(1)
• 下沉：对堆的根节点进行最大堆调整(Sift Down)： 对根节点元素进行下沉操作（根据当前节点的下标k，得到左孩子下标2k+1，右孩子下标2k+2，比较三个位置的值，如果左右孩子的最大值比父节点的值大，交换两个位置的值，递归直到没有孩子节点或满足都比左右孩子值大结束），使得堆维持大根堆的特性； O(log(N))

参考代码：com.chen.algorithm.sort.HeapSort

题目：随时找到数据流的中位数

牛客网-题库-在线编程-程序员代码面试指南-CD80-随时找到数据流的中位数

https://www.nowcoder.com/ta/programmer-code-interview-guide

有一个源源不断的吐出整数的数据流，假设你有足够的空间来保存吐出的数。请设计一个名叫MedianHolder的结构，MedianHolder可以随时取得之前吐出所有数的中位数。

[要求]

1. 如果MedianHolder已经保存了吐出的N个数，那么将一个新数加入到MedianHolder的过程，其时间复杂度是O(logN)。
2. 取得已经吐出的N个数整体的中位数的过程，时间复杂度为O(1)

解题方法一：

• 使用一个数组收集所有数据流输出的数，当需要获取中位数时，对数组进行排序，取出中间的数；
• 时间复杂度：O(n * logn)

解题方法二：

• 利用堆的特性，分别建立一个大根堆和一个小根堆，如果已经输出的数的总数为N，每个堆中存放N/2个数，同时维持小根堆中的数都是不小于大根堆中的数；当数据流中有数据输出时:
• 第一步：如果两个堆都为空将其放入大根堆；
• 第二步：输出的元素与大根堆中的堆顶元素比较，如果输出的元素较大，放入小根堆，同时执行Sift Up操作，维护小根堆的特性；否则放入大根堆中，执行Sift Up操作，维持大根堆的特性；
• 第三步：比较大根堆与小根堆的元素数量，两个堆的元素数量差值不超过1；否则：
  • 将数量多的堆，取出堆的根节点放入另一堆中，
  • 取出根节点的堆，根节点使用最后一个元素替换，堆的元素数量减1，执行Sift Down操作，维护该堆的特性；
  • 将取出的元素放到另一个堆的最后一个位置中，执行Sift Up操作，维护该堆的特性。
• 第四步：当需要获取已输出数据的中位数时，根据已输出数据总数N，以及大根堆和小根堆元素数量，来确定中位数是：大根堆的根节点（大根堆中的最大值）或 小根堆的根节点（小根堆中的最小值）。
• 时间复杂度：O(logn)

工程中的综合排序算法

• 如果待排序序列很长，判断数据类型
  • 如果是基础类型，使用快速排序；（基础类型相同值无差异）
  • 如果是自定义类型，使用归并排序；（保证稳定性）
• 如果待排序行序列很短(arr.length<60)，使用插入排序；
  • 插入排序时间复杂度为O(n^2)，但常数项很低，在小样本的情况下，插入排序反而更快

桶排序(bucket sort)、计数排序、基数排序(radix sort)的介绍

非基于比较的排序，与被排序的样本的实际数据状况很有关系，所以实际中并不经常使用；

时间复杂度：O(n) ，额外空间复杂度：O(n)

算法稳定性：稳定的排序

不基于比较的排序有一大类叫桶排序；

桶排序针对具体实现分为：计数排序、基数排序；

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

• 基数排序：根据键值的每位数字来分配桶；
• 计数排序：每个桶只存储单一键值；
• 桶排序：每个桶存储一定范围的数值；

计数排序案例

案例：一个待排序数组，其中所有数的值的范围为0~60，数组中包含60个数；

解题思路：

• 采用计数排序，计数排序是桶排序的一种具体实现；
• 不基于比较的排序，基于桶，桶是一种容器，一个桶就对应了一种数据状况出现的词频；
• 时间复杂度：O(n)
• 应用范围比较窄

解题方法：

• 初始生成一个长度为61的辅助数组，将数组中每一位的值置为0；
• 遍历待排序数组，根据数据的值，将辅助数组对应位置的值+1；
• 遍历辅助数组即可以获得有序的序列；

基数排序

原理是：

• 将整数按位数切割成不同的数字，然后按每个位数分别比较。
• 由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

基数排序的实现方法：

• LSD（Least significant digital）或 MSD（Most significant digital），
• LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

最低位优先(Least Significant Digit first)法，简称LSD法：

• 先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。

LSD示例：

• 待排序序列：3 44 38 5 47 15 36 26 27 2 46 4 19 50 48

LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。

MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。

最高位优先(Most Significant Digit first)法，简称MSD法：

• 先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，
• 之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。
• 再将各组连接起来，便得到一个有序序列。

处理包含负数的数据问题：

• 将所有的数加一个正数，使得所有的数变为正数进行基数排序；
• 排序完之后在减点加的正数值输出。

LSD实现代码：com.chen.algorithm.sort.LSDRadixSort

题目：求相邻两数的最大差值

LeetCode 164. 最大间距

https://leetcode-cn.com/problems/maximum-gap/

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。

如果数组元素个数小于 2，则返回 0。

你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。

要求时间复杂度O(N)，且要求不能使用非基于比较的排序。

示例：

输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。

解题思路：

• 设无序数组的元素数量为N，初始N+1个桶
• 找到无序数组的最小值min和最大值max，N+1个桶中存放的元素数量为：size = (max-min)/(N+1)，存放元素的大小依次为：min ~ (min + size)、(min + size) ~ (min + size*2)、逐个增加size；
• 遍历无序数组，将数组中的值放入对应范围的桶中；
• 因为元素数量是N，但有N+1个桶；所以肯定有一个桶为空；
• 一个桶内元素大小的最大差值不会超过size，且有一个桶为空，可以得出当排序后数组相邻两数的最大差值，肯定不会来自同一个桶内的两个数；
• 相邻元素之间的最大差值只可能来自相邻的两个桶；
• 每个桶存放的值为：该桶是否为空、该桶中元素的最大值、该桶中元素的最小值
• 遍历所有桶，比较相邻两桶的最小值和最大值，获得相邻两个数的最大差值，即可得出排序后数组的相邻两个元素的最大差值。

参考代码：com.chen.algorithm.sort.MaximumGap

使用基数排序 ：com.chen.algorithm.sort.MaximumGap2

相关链接

gitee地址：https://gitee.com/chentian114/chen_algorithm_study

github地址：https://github.com/chentian114/data-struct-and-algorithm

CSDN地址：https://blog.csdn.net/chentian114/category_9997109.html

公众号

参考

百度百科

左程云 牛客网 算法初级班课程

基数排序 | 菜鸟教程