大家好，我是老三，一个刷不动算法的程序员。排序算法相关题目尽管在力扣中不是很多，但是面试中动不动要手撕一下。接下来，我们看一下十大基本排序，

什么是排序算法的稳定性呢？

当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不惟一[1]。

在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的：

若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。

排序算法的稳定性

排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，那么这种排序算法就是不稳定的。

按在排序过程中是否涉及数据的内、外存交换来分类，排序大致分为两类：内部排序和外部排序。

按照是否通过比较来决定元素间的相对次序，排序可以分为比较类排序和非比较类排序。

排序分类

柿子挑软的捏，先从最简单的开始。

冒泡排序有着好听的名字，也有着最好理解的思路。

冒泡排序的基本思想是，从一端到另一端遍历，两两比较相邻元素的大小，如果是反序则交换。

动图如下（来源参考[4]）：

冒泡排序

先简单实现以下，很简单，两层循环，相邻元素比较：

  1.     public void sort(int[] nums) {
  2.         for (int i = 0; i < nums.length; i++) {
  3.             for (int j = i + 1; j < nums.length; j++) {
  4.                 //升序
  5.                 if (nums[i] > nums[j]) {
  6.                     //交换
  7.                     int temp = nums[i];
  8.                     nums[j] = nums[i];
  9.                     nums[i] = temp;
  10.                 }
  11.             }
  12.         }
  13.     }

上面的代码实现还存在一个问题，什么问题呢？

哪怕数组有序，它还是会接着遍历。

所以可以用一个标志位来标志数组是否有序，假如有序，就跳出遍历。

  1.    public void sort(int[] nums) {
  2.         //标志位
  3.         boolean flag = true;
  4.         for (int i = 0; i < nums.length; i++) {
  5.             for (int j = 0; j < nums.length - i - 1; j++) {
  6.                 //升序
  7.                 if (nums[j] > nums[j + 1]) {
  8.                     //交换
  9.                     int temp = nums[j];
  10.                     nums[j] = nums[j + 1];
  11.                     nums[j + 1] = temp;
  12.                 }
  13.             }
  14.             //如果是有序的,结束循环
  15.             if (flag) {
  16.                 break;
  17.             }
  18.         }
  19.     }

大小相同的元素没有交换位置，所以冒泡排序是稳定的。

算法名称 最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度 是否稳定
冒泡排序 O(n) O(n²) O(n²) O(1) 稳定

选择排序为什么叫选择排序？原理是怎么样的呢？

它的思路：首先在未排序的序列中找到最小或者最大的元素，放到排序序列的起始位置，然后再从未排序的序列中继继续寻找最小或者最大元素，然后放到已经排序序列的末尾。以此类推，直到所有元素排序完毕。

动图如下(来源参考[4])：

选择排序

来看一个例子，用选择排序的方式排序数组 [2,5,4,1,3]。

  • 第一趟，找到数组中最小的元素1，将它和数组的第一个元素交换位置。

选择排序1

  • 第二趟，在未排序的元素中找到最小的元素2，和数组的第二个元素交换位置。

选择排序2

  • 第三趟，在未排序的元素中找到最小的元素3，和数组的第三个元素交换位置。

选择排序-3

  • 第四趟，在未排序的元素中找到最小的元素4，和数组的第四个元素交换位置。

选择排序4

那么到这，我们的数组就是有序的了。

选择排序5

选择排序的思路很简单，实现起来也不难。

  1.     public void sort(int[] nums) {
  2.         int min = 0;
  3.         for (int i = 0; i < nums.length - 1; i++) {
  4.             for (int j = i + 1; j < nums.length; j++) {
  5.                 //寻找最小的数
  6.                 if (nums[j] < min) {
  7.                     min = j;
  8.                 }
  9.             }
  10.             //交换
  11.             int temp = nums[i];
  12.             nums[i] = nums[min];
  13.             nums[min] = temp;
  14.         }
  15.     }

选择排序稳定吗？

答案是不稳定的，因为在未排序序列中找到最小值之后，和排序序列的末尾元素交换。

算法名称 最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度 是否稳定
选择排序 O(n²) O(n²) O(n²) O(1) 不稳定

关于插入排序，有一个非常形象的比喻。斗地主——摸到的牌都是乱的，我们会把摸到的牌插到合适的位置。

它的思路：将一个元素插入到已经排好序的有序序列中，从而得到一个新的有序序列。

动图如下(来源参考3)：

插入排序

还是以数组 [2,5,4,1,3]为例：

  • 第一趟：从未排序的序列将元素5插入到已排序的序列的合适位置

插入排序1

  • 第二趟：接着从未排序的序列中，将元素4插入到已经排序的序列的合适位置，需要遍历有序序列，找到合适的位置

插入排序2

  • 第三趟：继续，把1插入到合适的位置

插入排序4

  • 第五趟：继续，把3插入到合适的位置

插入排序5

OK，排序结束。

找到插入元素的位置，移动其它元素。

  1.     public void sort(int[] nums) {
  2.         //无序序列从1开始
  3.         for (int i = 1; i < nums.length; i++) {
  4.             //需要插入有序序列的元素
  5.             int value = nums[i];
  6.             int j = 0;
  7.             for (j = i - 1; j >= 0; j--) {
  8.                 //移动数据
  9.                 if (nums[j] > value) {
  10.                     nums[j + 1] = nums[j];
  11.                 } else {
  12.                     break;
  13.                 }
  14.             }
  15.             //插入元素
  16.             nums[j + 1] = value;
  17.         }
  18.     }

插入排序智慧移动比插入元素大的元素，所以相同元素相对位置不变，是稳定的。

从代码里我们可以看出，如果找到了合适的位置，就不会再进行比较了，所以最好情况时间复杂度是O(n)。

算法名称 最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度 是否稳定
插入排序 O(n) O(n²) O(n²) O(1) 稳定

希尔排序，名字来自它的发明者Shell。它是直接插入排序的改进版。

希尔排序的思路是：把整个待排序的记录序列分割成若干个子序列，分别进行插入排序。

我们知道直接插入排序在面对大量无序数据的时候不太理想，希尔排序就是通过跳跃性地移动，来达到数组元素地基本有序，再接着用直接插入排序。

希尔排序动图（动图来源参考[1]）：

希尔排序

还是以数组 [2,5,6,1,7，9，3，8，4]为例，我们来看一下希尔排序的过程：

  • 数组元素个数为9，取7/2=4为下标差值，将下标差值为4的元素分为一组

希尔排序-1

  • 组内进行插入排序，构成有序序列

希尔排序-2

  • 再取4/2=2为 下标差值，将下标差值为2的元素分为一组

希尔排序3

  • 组内插入排序，构成有序序列

希尔排序4

  • 下标差值=2/2=1，将剩余的元素插入排序

希尔排序5

可以看看前面的插入排序，希尔排序

只是一个有步长的直接插入排序。

  1.     public void sort(int[] nums){
  2.         //下标差
  3.         int step=nums.length;
  4.         while (step>0){
  5.             //这个是可选的，也可以是3
  6.             step=step/2;
  7.             //分组进行插入排序
  8.             for (int i=0;i<step;i++){
  9.                 //分组内的元素，从第二个开始
  10.                 for (int j=i+step;j<nums.length;j+=step){
  11.                     //要插入的元素
  12.                     int value=nums[j];
  13.                     int k;
  14.                     for (k=j-step;k>=0;k-=step){
  15.                       if (nums[k]>value){
  16.                           //移动组内元素
  17.                           nums[k+step]=nums[k];
  18.                       }else {
  19.                           break;
  20.                       }
  21.                     }
  22.                     //插入元素
  23.                     nums[k+step]=value;
  24.                 }
  25.             }
  26.         }
  27.     }
  • 稳定度分析

希尔排序是直接插入排序的变形，但是和直接插入排序不同，它进行了分组，所以不同组的相同元素的相对位置可能会发生改变，所以它是不稳定的。

  • 时间复杂度分析

希尔排序的时间复杂度跟增量序列的选择有关，范围为 O(n^(1.3-2)) 在此之前的排序算法时间复杂度基本都是 O(n²)，希尔排序是突破这个时间复杂度的第一批算法之一。

算法名称 时间复杂度 空间复杂度 是否稳定
希尔排序 O(n^(1.3-2)) O(1) 不稳定

归并排序是建立在归并操作上的一种有效的排序算法，归并，就是合并的意思，在数据结构上的定义就是把把若干个有序序列合并成一个新的有序序列。

归并排序是分治法的典型应用，分治什么意思呢？就是把一个大的问题分解成若干个小的问题来解决。

归并排序的步骤，是把一个数组切分成两个，接着递归，一直到单个元素，然后再合并，单个元素合并成小数组，小数组合并成大数组。

动图如下（来源参考[4]）：

归并排序

我们以数组[2,5,6,1,7,3,8,4] 为例，来看一下归并排序的过程：

归并排序

拆分就不用多讲了，我们看看怎么合并。

这里使用递归来实现归并排序：

  • 递归终止条件

递归起始位置小于终止位置

  • 递归返回结果

直接对传入的数组序列进行排序，所以无返回值

  • 递归逻辑

将当前数组分成两组，分别分解两组，最后归并

代码如下：

  1. public class MergeSort {
  3.     public void sortArray(int[] nums) {
  4.         sort(nums, 0, nums.length - 1);
  5.     }
  7.     /**
  8.      * 归并排序
  9.      *
  10.      * @param nums
  11.      * @param left
  12.      * @param right
  13.      */
  14.     public void sort(int[] nums, int left, int right) {
  15.         //递归结束条件
  16.         if (left >= right) {
  17.             return;
  18.         }
  19.         int mid = left + (right - left) / 2;
  20.         //递归当前序列左半部分
  21.         sort(nums, left, mid);
  22.         //递归当前序列右半部分
  23.         sort(nums, mid + 1, right);
  24.         //归并结果
  25.         merge(nums, left, mid, right);
  26.     }
  28.     /**
  29.      * 归并
  30.      *
  31.      * @param arr
  32.      * @param left
  33.      * @param mid
  34.      * @param right
  35.      */
  36.     public void merge(int[] arr, int left, int mid, int right) {
  37.         int[] tempArr = new int[right - left + 1];
  38.         //左边首位下标和右边首位下标
  39.         int l = left, r = mid + 1;
  40.         int index = 0;
  41.         //把较小的数先移到新数组中
  42.         while (l <= mid && r <= right) {
  43.             if (arr[l] <= arr[r]) {
  44.                 tempArr[index++] = arr[l++];
  45.             } else {
  46.                 tempArr[index++] = arr[r++];
  47.             }
  48.         }
  49.         //把左边数组剩余的数移入数组
  50.         while (l <= mid) {
  51.             tempArr[index++] = arr[l++];
  52.         }
  53.         //把右边剩余的数移入数组
  54.         while (r <= right) {
  55.             tempArr[index++] = arr[r++];
  56.         }
  57.         //将新数组的值赋给原数组
  58.         for (int i = 0; i < tempArr.length; i++) {
  59.             arr[i+left] = tempArr[i];
  60.         }
  61.     }
  62. }
  • 时间复杂度

一趟归并，我们需要把遍历待排序序列遍历一遍，时间复杂度O(n)。

而归并排序的过程，需要把数组不断二分，这个时间复杂度是O(logn)。

所以归并排序的时间复杂度是O(nlogn)。

  • 空间复杂度

使用了一个临时数组来存储合并的元素，空间复杂度O(n)。

  • 稳定性

归并排序是一种稳定的排序方法。

算法名称 最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度 是否稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定

快速排序是面试最高频的排序算法。

快速排序和上面的归并排序一样，都是基于分治思想的，大概过程：

  • 选出一个基准数，基准值一般取序列最左边的元素
  • 重新排序序列，比基准值小的放在基准值左边，比基准值大的放在基准值右边，这就是所谓的分区

快速排序动图如下：

快速排序动图

我们来看一个完整的快速排序图示：

快速排序

选择一个数作为基准数pivot，同时设定一个标记 mark 代表左边序列最右侧的下标位置，接下来遍历数组，如果元素大于基准值，无操作，继续遍历，如果元素小于基准值，则把 mark + 1 ，再将 mark 所在位置的元素和遍历到的元素交换位置，mark 这个位置存储的是比基准值小的数据，当遍历结束后，将基准值与 mark 所在元素交换位置。

  1. public class QuickSort0 {
  3.     public void sort(int[] nums) {
  4.         quickSort(nums, 0, nums.length - 1);
  5.     }
  7.     public void quickSort(int[] nums, int left, int right) {
  8.         //结束条件
  9.         if (left >= right) {
  10.             return;
  11.         }
  12.         //分区
  13.         int partitonIndex = partion(nums, left, right);
  14.         //递归左分区
  15.         quickSort(nums, left, partitonIndex - 1);
  16.         //递归右分区
  17.         quickSort(nums, partitonIndex + 1, right);
  18.     }
  20.     //分区
  21.     public int partion(int[] nums, int left, int right) {
  22.         //基准值
  23.         int pivot = nums[left];
  24.         //mark标记初始下标
  25.         int mark = left;
  26.         for (int i = left + 1; i <= right; i++) {
  27.             if (nums[i] < pivot) {
  28.                 //小于基准值，则mark+1，并交换位置
  29.                 mark++;
  30.                 int temp = nums[mark];
  31.                 nums[mark] = nums[i];
  32.                 nums[i] = temp;
  33.             }
  34.         }
  35.         //基准值与mark对应元素调换位置
  36.         nums[left] = nums[mark];
  37.         nums[mark] = pivot;
  38.         return mark;
  39.     }
  40. }

还有另外一种双边扫描的做法。

选择一个数作为基准值，然后从数组左右两边进行扫描，先从左往右找到一个大于基准值的元素，将它填入到right指针位置，然后转到从右往左扫描，找到一个小于基准值的元素，将他填入到left指针位置。

  1. public class QuickSort1 {
  3.     public int[] sort(int[] nums) {
  5.         quickSort(nums, 0, nums.length - 1);
  6.         return nums;
  8.     }
  10.     public void quickSort(int[] nums, int low, int high) {
  12.         if (low < high) {
  13.             int index = partition(nums, low, high);
  14.             quickSort(nums, low, index - 1);
  15.             quickSort(nums, index + 1, high);
  16.         }
  18.     }
  20.     public int partition(int[] nums, int left, int right) {
  21.         //基准值
  22.         int pivot = nums[left];
  23.         while (left < right) {
  24.             //从右往左扫描
  25.             while (left < right && nums[right] >= pivot) {
  26.                 right--;
  27.             }
  28.             //找到第一个比pivot小的元素
  29.             if (left < right) nums[left] = nums[right];
  30.             //从左往右扫描
  31.             while (left < right && nums[left] <= pivot) {
  32.                 left++;
  33.             }
  34.             //找到第一个比pivot大的元素
  35.             if (left < right) nums[right] = nums[left];
  36.         }
  37.         //基准数放到合适的位置
  38.         nums[left] = pivot;
  39.         return left;
  40.     }
  41. }
  • 时间复杂度

快速排序的时间复杂度和归并排序一样，都是O(nlogn)，但是这是最优的情况，也就是每次都能把数组切分到两个差不多大小的子数组。

如果出现极端情况，例如一个有序的序列[5,4,3,2,1] ，选基准值为5，那么需要切分n-1次才能完成整个快速排序的过程，这种情况时间复杂度就退化到了O(n²)。

  • 空间复杂度

快速排序是一种原地排序的算法，空间复杂度是O(1)。

  • 稳定性

快排的比较和交换是跳跃进行的，所以快排是一种不稳定的排序算法。

算法名称 最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度 是否稳定
快速排序 O(nlogn) O(n²) O(nlogn) O(1) 不稳定

还记得我们前面的简单选择排序吗？堆排序是简单选择排序的一种升级版。

在学习堆排序之前，什么是堆呢？

完全二叉树是堆的一个比较经典的堆实现。

我们先来了解一下什么是完全二叉树。

简答说，如果节点不满，那它不满的部分只能在最后一层的右侧。

我们来看几个示例。

完全二叉树和非完全二叉树

相信看了这几个示例，就清楚什么是完全二叉树，什么是非完全二叉树。

那堆又是什么呢？

  • 必须是完全二叉树
  • 任一节点的值必须是其子树的最大值或最小值
  • 最大值时，称为“最大堆”，也称大顶堆；
  • 最小值时，称为“最小堆”，也称小顶堆。

大、小顶堆

因为堆是完全二叉树，所以堆可以用数组存储。

按层来将元素存储到数组对应位置，从下标1开始存储，可以省略一些计算。

大顶堆存储

好了，我们现在对堆已经有一些了解了，我们来看一下堆排序是什么样的呢？[2]

  • 建立一个大顶堆
  • 将堆顶元素（最大值）插入数组末尾
  • 让新的最大元素上浮到堆顶
  • 重复过程，直到排序完成

动图如下（来源参考[1]）：

堆排序动图（来自参考[1]）

关于建堆，有两种方式，一种是上浮，一种是下沉。

上浮是什么呢？就是把子节点一层层上浮到合适的位置。

下沉是什么呢？就是把堆顶元素一层层下沉到合适的位置。

上面的动图，使用的就是下沉的方式。

  1. public class HeapSort {
  3.     public void sort(int[] nums) {
  4.         int len = nums.length;
  5.         //建堆
  6.         buildHeap(nums, len);
  7.         for (int i = len - 1; i > 0; i--) {
  8.             //将堆顶元素和堆末元素调换
  9.             swap(nums, 0, i);
  10.             //数组计数长度减1，隐藏堆尾元素
  11.             len--;
  12.             //将堆顶元素下沉，使最大的元素浮到堆顶来
  13.             sink(nums, 0, len);
  14.         }
  15.     }
  17.     /**
  18.      * 建堆
  19.      *
  20.      * @param nums
  21.      * @param len
  22.      */
  23.     public void buildHeap(int[] nums, int len) {
  24.         for (int i = len / 2; i >= 1; i--) {
  25.             //下沉
  26.             sink(nums, i, len);
  27.         }
  28.     }
  30.     /**
  31.      * 下沉操作
  32.      *
  33.      * @param nums
  34.      * @param index
  35.      * @param end
  36.      */
  37.     public void sink(int[] nums, int index, int end) {
  38.         //左子节点下标
  39.         int leftChild = 2 * index + 1;
  40.         //右子节点下标
  41.         int rightChild = 2 * index + 2;
  42.         //要调整的节点下标
  43.         int current = index;
  44.         //下沉左子树
  45.         if (leftChild < end && nums[leftChild] > nums[current]) {
  46.             current = leftChild;
  47.         }
  48.         //下沉右子树
  49.         if (rightChild < end && nums[rightChild] > nums[current]) {
  50.             current = rightChild;
  51.         }
  52.         //如果下标不相等，证明调换过了
  53.         if (current!=index){
  54.             //交换值
  55.             swap(nums,index,current);
  56.             //继续下沉
  57.             sink(nums,current,end);
  58.         }
  59.     }
  61.     public void swap(int[] nums, int i, int j) {
  62.         int temp = nums[i];
  63.         nums[i] = nums[j];
  64.         nums[j] = temp;
  65.     }
  66. }
  • 时间复杂度

堆排的时间复杂度和快排的时间复杂度一样，都是O(nlogn)。

  • 空间复杂度

堆排没有引入新的空间，原地排序，空间复杂度O(1)。

  • 稳定性

堆顶的元素不断下沉，交换，会改变相同元素的相对位置，所以堆排是不稳定的。

算法名称 时间复杂度 空间复杂度 是否稳定
堆排序 O(nlogn) O(1) 不稳定

文章开始我们说了，排序分为比较类和非比较类，计数排序是一种非比较类的排序方法。

计数排序是一种线性时间复杂度的排序，利用空间来换时间，我们来看看计数排序是怎么实现的吧。

计数排序的大致过程[4]：

  • 找出待排序的数组中最大和最小的元素
  • 统计数组中每个值为i的元素出现的次数，存入数组arr的第i项；
  • 对所有的计数累加（从arr中的第一个元素开始，每一项和前一项相加）；
  • 反向填充目标数组：将每个元素i放在新数组的第arr(i)项，每放一个元素就将arr(i)减去1。

我们看一下动图演示（来自参考[4]）：

计数排序动图，来自参考[4]

我们拿一个数组来看一下完整过程：[6,8,5,1,2,2,3]

  • 首先，找到数组中最大的数，也就是8，创建一个最大下标为8的空数组arr

计数排序-1

  • 遍历数据，将数据的出现次数填入arr对应的下标位置中

计数排序-2

  • 然后输出数组元素的下标值，元素的值是几，就输出几次

计数排序-3

  1. public class CountSort {
  3.     public void sort(int[] nums) {
  4.         //查找最大值
  5.         int max = findMax(nums);
  6.         //创建统计次数新数组
  7.         int[] countNums = new int[max + 1];
  8.         //将nums元素出现次数存入对应下标
  9.         for (int i = 0; i < nums.length; i++) {
  10.             int num = nums[i];
  11.             countNums[num]++;
  12.             nums[i] = 0;
  13.         }
  14.         //排序
  15.         int index = 0;
  16.         for (int i = 0; i < countNums.length; i++) {
  17.             while (countNums[i] > 0) {
  18.                 nums[index++] = i;
  19.                 countNums[i]--;
  20.             }
  21.         }
  22.     }
  24.     public int findMax(int[] nums) {
  25.         int max = nums[0];
  26.         for (int i = 0; i < nums.length; i++) {
  27.             if (nums[i] > max) {
  28.                 max = nums[i];
  29.             }
  30.         }
  31.         return max;
  32.     }
  33. }

OK，乍一看没啥问题，但是仔细想想，其实还是有些毛病的，毛病在哪呢？

  • 如果我们要排序的元素有0怎么办呢？例如[0,0,5,2,1,3,4] ，arr初始都为0，怎么排呢？

    这个很难解决，有一种办法，就是计数的时候原数组先加10，[-1,0,2]，排序写回去的时候再减，但是如果刚好碰到有-10这个元素就凉凉。

  • 如果元素的范围很大呢？例如[9992,9998,9993,9999]，那我们申请一个10000个元素的数组吗？

    这个可以用偏移量解决，找到最大和最小的元素，计算偏移量，例如[9992,9998,9993,9999]，偏移量=9999-9992=7，我们只需要建立一个容量为8的数组就可以了。

解决第二个问题的版本如下：

  1. public class CountSort1 {
  3.     public void sort(int[] nums) {
  4.         //查找最大值
  5.         int max = findMax(nums);
  6.         //寻找最小值
  7.         int min = findMin(nums);
  8.         //偏移量
  9.         int gap = max - min;
  10.         //创建统计次数新数组
  11.         int[] countNums = new int[gap + 1];
  12.         //将nums元素出现次数存入对应下标
  13.         for (int i = 0; i < nums.length; i++) {
  14.             int num = nums[i];
  15.             countNums[num - min]++;
  16.             nums[i] = 0;
  17.         }
  18.         //排序
  19.         int index = 0;
  20.         for (int i = 0; i < countNums.length; i++) {
  21.             while (countNums[i] > 0) {
  22.                 nums[index++] = min + i;
  23.                 countNums[i]--;
  24.             }
  25.         }
  26.     }
  28.     public int findMax(int[] nums) {
  29.         int max = nums[0];
  30.         for (int i = 0; i < nums.length; i++) {
  31.             if (nums[i] > max) {
  32.                 max = nums[i];
  33.             }
  34.         }
  35.         return max;
  36.     }
  38.     public int findMin(int[] nums) {
  39.         int min = nums[0];
  40.         for (int i = 0; i < nums.length; i++) {
  41.             if (nums[i] < min) {
  42.                 min = nums[i];
  43.             }
  44.         }
  45.         return min;
  46.     }
  47. }
  • 时间复杂度

我们整体运算次数是n+n+n+k=3n+k，所以使劲复杂度是O(n+k)。

  • 空间复杂度

引入了辅助数组，空间复杂度O(n)。

  • 稳定性

我们的实现实际上是不稳定的，但是计数排序是有稳定的实现的，可以查看参考[1]。

同时我们通过实现也发现，计数排序实际上不适合有负数的，元素偏移值过大的数组。

桶数组可以看做计数排序的升级版，它把元素分到若干个桶中，每个桶中的元素再单独排序。

桶排序大概的过程：

  • 设置一个定量的数组当作空桶；
  • 遍历输入数据，并且把元素一个一个放到对应的桶里去；
  • 对每个不是空的桶进行排序；
  • 从不是空的桶里把排好序的数据拼接起来。

桶排序动图如下（动图来源参考[1]）：

桶排序动图（来源参考[1]）

我们上面说了，计数排序不适合偏移量过大的数组，我们拿一个偏移量非常大的数组[2066,566,166，66,1066，2566，1566]为例，来看看桶排序的过程。

  • 创建6个桶，分别存储0-500,500-1000,1000-1500,1500-2000,2000-2500,2500-3000的元素

桶排序-1

  • 遍历数组，将元素分别分配到对应的桶中

桶排序-2

  • 桶中元素排序，这里我们明显只用排序第一个桶

桶排序-3

  • 将桶中的元素依次取出，取出的元素就是有序的了

桶排序-4

桶排序的实现我们要考虑几个问题：

  • 桶该如何表示？
  • 桶的数量怎么确定？
  • 桶内排序用什么方法？

我们来看一下代码：

  1. public class BucketSort {
  3.     public void sort(int[] nums) {
  4.         int len = nums.length;
  5.         int max = nums[0];
  6.         int min = nums[0];
  7.         //获取最大值和最小值
  8.         for (int i = 1; i < len; i++) {
  9.             if (nums[i] > max) {
  10.                 max = nums[i];
  11.             }
  12.             if (nums[i] < min) {
  13.                 min = nums[i];
  14.             }
  15.         }
  16.         //计算步长
  17.         int gap = max - min;
  18.         //使用列表作为桶
  19.         List<List<Integer>> buckets = new ArrayList<>();
  20.         //初始化桶
  21.         for (int i = 0; i < gap; i++) {
  22.             buckets.add(new ArrayList<>());
  23.         }
  24.         //确定桶的存储区间
  25.         int section = gap / len - 1;
  26.         //数组入桶
  27.         for (int i = 0; i < len; i++) {
  28.             //判断元素应该入哪个桶
  29.             int index = nums[i] / section - 1;
  30.             if (index < 0) {
  31.                 index = 0;
  32.             }
  33.             //对应的桶添加元素
  34.             buckets.get(index).add(nums[i]);
  35.         }
  36.         //对桶内的元素排序
  37.         for (int i = 0; i < buckets.size(); i++) {
  38.             //这个底层调用的是 Arrays.sort
  39.             // 这个api不同情况下可能使用三种排序：插入排序，快速排序，归并排序，具体看参考[5]
  40.             Collections.sort(buckets.get(i));
  41.         }
  42.         //将桶内的元素写入原数组
  43.         int index = 0;
  44.         for (List<Integer> bucket : buckets) {
  45.             for (Integer num : bucket) {
  46.                 nums[index] = num;
  47.                 index++;
  48.             }
  49.         }
  50.     }
  51.     
  52. }
  • 时间复杂度

桶排序最好的情况，就是元素均匀分配到了每个桶，时间复杂度O(n)，最坏情况，是所有元素都分配到一个桶中，时间复杂度是O(n²)。平均的时间复杂度和技术排序一样，都是O(n+k)。

  • 空间复杂度

桶排序，需要存储n个额外的桶，桶中又要存储k个元素，所以空间复杂度是O(n+k)。

  • 稳定性

稳定性得看桶中排序用的什么排序算法，桶中用的稳定排序算法，那么就是稳定的。用的不稳定的排序算法，那么就是不稳定的。

基数排序是一种非比较型的排序方法。

它的基本原理是将元素按照位数切割成不同的数字，然后按照每个位数进行比较。

大概过程：

  • 取得数组中的最大数，并取得位数；
  • arr为原始数组，从最低位开始取每个位组成radix数组
  • 对radix进行计数排序（利用计数排序适用于小范围数的特点）

动图图示如下（来源参考[1]）：

基数排序-来源参考[1]

基数排序可以说是桶排序的一个进化，我们以 [ 892， 846， 821， 199， 810，700 ]来看一下基数排序的过程：

  • 创建十个桶用来存储元素

桶排序-1

  • 根据个位数，将元素分别分配到不同的桶中

基数排序-2

  • 然后将桶中的元素依次取出

基数排序-3

  • 接下来排十位数，根据十位数分配桶，再依次取出

基数排序-3

  • 接下来百位数

基数排序-4

  1. public class RadixSort {
  3.     public void sort(int[] nums) {
  4.         int len = nums.length;
  5.         //最大值
  6.         int max = nums[0];
  7.         for (int i = 0; i < len; i++) {
  8.             if (nums[i] > max) {
  9.                 max = nums[i];
  10.             }
  11.         }
  12.         //当前排序位置
  13.         int location = 1;
  14.         //用列表实现桶
  15.         List<List<Integer>> buckets = new ArrayList<>();
  16.         //初始化size为10的一个桶
  17.         for (int i = 0; i < 10; i++) {
  18.             buckets.add(new ArrayList<>());
  19.         }
  20.         while (true) {
  21.             //元素最高位数
  22.             int d = (int) Math.pow(10, (location - 1));
  23.             //判断是否排完
  24.             if (max < d) {
  25.                 break;
  26.             }
  27.             //数据入桶
  28.             for (int i = 0; i < len; i++) {
  29.                 //计算余数 放入相应的桶
  30.                 int number = ((nums[i] / d) % 10);
  31.                 buckets.get(number).add(nums[i]);
  32.             }
  33.             //写回数组
  34.             int nn = 0;
  35.             for (int i = 0; i < 10; i++) {
  36.                 int size = buckets.get(i).size();
  37.                 for (int ii = 0; ii < size; ii++) {
  38.                     nums[nn++] = buckets.get(i).get(ii);
  39.                 }
  40.                 buckets.get(i).clear();
  41.             }
  42.             location++;
  43.         }
  44.     }
  45. }
  • 时间复杂度

时间复杂度O(n+k)，其中n数组元素个数，k为数组元素最高位数。

  • 空间复杂度

和桶排序一样，因为引入了桶的存储空间，所以空间复杂度O(n+k)。

  • 稳定性

因为基数排序过程，每次都是将当前位数是哪个相同数值的元素统一分配到桶中，并不交换位置，所以基数排序是稳定的。

这篇文章，我们学习了十大基本排序，来简单总结一下。

首先最简单的冒泡排序：两层循环，相邻交换；

选择排序：未排序和排序两分，从未排序序列中寻找最小的元素，放在排序序列末尾；

插入排序：斗地主摸牌思维，把一个元素插入到有序序列合适位置；

希尔排序：插入排序plus，先把序列分割，再分别插入排序；

归并排序：分治思想第一弹，先将序列切分，再在合并过程排序；

快速排序：分治思想第二弹，基准数分区原序列，小的放左边，大的放右边；

堆排序：选择排序plus，建立大顶堆，堆顶元素（最大值）插入序列末尾，再让新的元素上浮。

计数排序：空间换时间第一弹，利用新数组，统计对应元素出现次数，输出新数组下标，原数组完成排序；

桶排序：空间换时间第二弹，将原数组的元素分到若干个桶，每个桶单独排序，再把桶里元素拼起来；

基数排序：空间换时间第三弹，桶排序plus，根据数位，把元素分桶，然后按每个位数比较。

十大基本排序性能汇总：

排序方法 时间复杂度（平均） 时间复杂度（最坏） 时间复杂度（最好） 空间复杂度 稳定性
冒泡排序 O(n²) O(n²) O(n) O(1) 稳定
选择排序 O(n²) O(n²) O(n²) O(1) 不稳定
插入排序 O(n²) O(n²) O(n) O(1) 稳定
希尔排序 O(n^(1.3-2)) O(n²) O(n) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
快速排序 O(nlogn) O(n²) O(nlogn) O(nlogn) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
计数排序 O(n+k) O(n+k) O(n+k) O(n) 稳定
桶排序 O(n+k) O(n²) O(n) O(n+k) 稳定
基数排序 O(n*k) O(n*k) O(n*k) O(n+k) 稳定

简单的事情重复做，重复的事情认真做，认真的事情有创造性地去做。

我是三分恶，一个能文能武的全栈开发。

点赞、关注 不迷路，咱们下期见！

参考：

[1].这或许是东半球分析十大排序算法最好的一篇文章

[2]. https://github.com/chefyuan/algorithm-base

[2].《数据结构与算法分析》

[3]. 面试高频：Java常用的八大排序算法一网打尽！

[4]. 十大经典排序算法（动图演示）

[5]. 剖析JDK8中Arrays.sort底层原理及其排序算法的选择

版权声明：本文为three-fighter原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/three-fighter/p/15229203.html