0. 前言
大家好，我是多选参数的程序锅，一个正在捣鼓操作系统、学数据结构和算法以及 Java 的失业人员。数据结构和算法我已经学了有一段日子了，最近也开始在刷 LeetCode 上面的题目了，但是自己感觉在算法上还是 0 ，还得猛补啊。
今天这篇基于之前的 8 大排序算法基础之上，增加一个堆排序，也就是这么 9 个排序算法：冒泡排序、插入排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。它们对应的时间复杂度如下所示：
| 排序算法 |
时间复杂度 |
是否基于比较 |
| 冒泡、插入、选择 |
O(n^2) |
√ |
| 快排、归并、堆排序 |
O(nlogn) |
√ |
| 桶、计数、基数 |
O(n) |
× |
整篇文章的主要知识提纲如图所示，本篇相关的代码都可以从 https://github.com/DawnGuoDev/algorithm 获取，另外，该仓库除了包含了基础的数据结构和算法实现之外，还会有数据结构和算法的笔记、LeetCode 刷题记录（多种解法、Java 实现） 、一些优质书籍整理。
![]()
★
本文的图很多都是从极客时间王争老师专栏那边拷贝过来或者截图过来的，少部分图是自己重新画的。为什么不全都换成自己画的图？主要是我比较懒，我觉得图能将自己要阐述的点解释清楚，或者说和自己整理过后的文字结合的不错，我觉得这个图就没必要重新画了，人家的画已经很好看了，也很清晰了，你将它重新画，其实也是差不多，可能就是换个样式而已，核心的东西还是没有变。但是，在有些地方，我觉得别人的图跟我阐述的内容不符合，或者不能很好地阐述我想表达的东西，又或者这个地方需要一个图，那么我会画一个。
”
1. 排序算法分析
学习排序算法除了学习它的算法原理、代码实现之外，最重要的是学会如何评价、分析一个排序算法。分析一个排序算法通常从以下几点出发。
1.1. 执行效率
而对执行效率的分析，一般从这几个方面来衡量：
-
最好情况、最坏情况、平均情况
除了需要给出这三种情况下的时间复杂度还要给出对应的要排序的原始数据是怎么样的。
-
时间复杂度的系数、常数、低阶
大 O 时间复杂度反应的是算法时间随 n 的一个增长趋势，比如 O(n^2) 表示算法时间随 n 的增加，呈现的是平方的增长趋势。这种情况下往往会忽略掉系数、常数、低阶等。但是实际开发过程中，排序的数据往往是 10 个、100 个、1000 个这样规模很小的数据，所以在比较同阶复杂度的排序算法时，这些系数、常数、低阶不能省略。
-
比较次数和交换（或移动）次数
在基于比较的算法中，会涉及到元素比较和元素交换等操作。所以分析的时候，还需要对比较次数和交换次数进行分析。
1.2. 内存消耗
内存消耗其实就是空间复杂度。针对排序算法来说，如果该排序算法的空间复杂度为 O(1)，那么这个排序算法又称为原地排序。
1.3. 稳定性
是什么
稳定性是指待排序的序列中存在值相等的元素。在排序之后，相等元素的前后顺序跟排序之前的是一样的。
为什么
我们将排序的原理和实现排序时用的大部分都是整数，但是实际开发过程中要排序的往往是一组对象，而我们只是按照对象中的某个 key 来进行排序。
比如一个对象有两个属性，下单时间和订单金额。在存入到数据库的时候，这些对象已经按照时间先后的顺序存入了。但是我们现在要以订单金额为主要 key，在订单金额相同的时候，以下单时间为 key。那么在采用稳定的算法之后，只需要按照订单金额进行一次排序即可。比如有这么三个数据，第一个数据是下单时间、第二数据是订单金额：（20200515、20）、（20200516、10）、（20200517、30）、（20200518、20）。在采用稳定的算法之后，排序的情况如下：（20200516、10）、(20200515、20)、（20200518、20）、（20200517、30）可以发现在订单金额相同的情况下是按订单时间进行排序的。
2. 经典的常用排序算法
2.1. 冒泡排序
冒泡排序就是依次对两个相邻的元素进行比较，然后在不满足大小条件的情况下进行元素交换。一趟冒泡排序下来至少会让一个元素排好序（元素排序好的区域相当于有序区，因此冒泡排序中相当于待排序数组分成了两个已排序区间和未排序区间）。因此为了将 n 个元素排好序，需要 n-1 趟冒泡排序（第 n 趟的时候就不需要）。
下面用冒泡排序对这么一组数据4、5、6、3、2、1，从小到大进行排序。第一次排序情况如下：
![]()
可以看出，经过一次冒泡操作之后，6 这个元素已经存储在正确的位置上了，要想完成有所有数据的排序，我们其实只需要 5 次这样的冒泡排序就行了。图中给出的是带第 6 次了的，但是第 6 次其实没必要。
![]()
2.1.1. 优化
使用冒泡排序的过程中，如果有一趟冒泡过程中元素之间没有发生交换，那么就说明已经排序好了，可以直接退出不再继续执行后续的冒泡操作了。
2.1.2. 实现
下面的冒泡排序实现是优化之后的：
/**
* 冒泡排序：
* 以升序为例，就是比较相邻两个数，如果逆序就交换，类似于冒泡；
* 一次冒泡确定一个数的位置，因为要确定 n-1 个数，因此需要 n-1
* 次冒泡；
* 冒泡排序时，其实相当于把整个待排序序列分为未排序区和已排序区
*/
public void bubbleSort(int[] arr, int len) {
// len-1 趟
for (int j = 0; j < len-1; j++) {
int sortedFlag = 0;
// 一趟冒泡
for (int i = 0; i < len-1-j; i++) {
if (arr[i] > arr[i+1]) {
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
sortedFlag = 1;
}
}
// 该趟排序中没有发生，表示已经有序
if (0 == sortedFlag) {
break;
}
}
}
2.1.3. 算法分析
2.2. 插入排序
**插入排序中将数组中的元素分成两个区间：已排序区间和未排序区间（最开始的时候已排序区间的元素只有数组的第一个元素），插入排序就是将未排序区间的元素依次插入到已排序区间（需要保持已排序区间的有序）。最终整个数组都是已排序区间，即排序好了。**假设要对 n 个元素进行排序，那么未排序区间的元素个数为 n-1，因此需要 n-1 次插入。插入位置的查找可以从尾到头遍历已排序区间也可以从头到尾遍历已排序区间。
如图所示，假设要对 4、5、6、1、3、2进行排序。左侧橙红色表示的是已排序区间，右侧黄色的表示未排序区间。整个插入排序过程如下所示
![]()
2.2.1. 优化
2.2.2. 实现
这边查找插入位置的方式采用从尾到头遍历已排序区间，也没有使用哨兵。
/**
* 插入排序：
* 插入排序也相当于把待排序序列分成已排序区和未排序区；
* 每趟排序都将从未排序区选择一个元素插入到已排序合适的位置；
* 假设第一个元素属于已排序区，那么还需要插入 len-1 趟；
*/
public void insertSort(int[] arr, int len) {
// len-1 趟
for (int i = 1; i < len; i++) {
// 一趟排序
int temp = arr[i];
int j;
for (j = i-1; j >= 0; j--) {
if (arr[j] > temp) {
arr[j+1] = arr[j];
} else {
break;
}
}
arr[j+1] = temp;
}
}
2.2.3. 算法分析
2.2.4. VS 冒泡排序
冒泡排序和插入排序的时间复杂度都是 O(n^2)，都是原地稳定排序。而且冒泡排序不管怎么优化，元素交换的次数是一个固定值，是原始数据的逆序度。插入排序是同样的，不管怎么优化，元素移动的次数也等于原始数据的逆序度。但是，从代码的实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要 3 个赋值操作，而插入排序只需要一个赋值操作。所以，虽然冒泡排序和插入排序在时间复杂度上都是 O(n^2)，但是如果希望把性能做到极致，首选插入排序。其实该点分析的主要出发点就是在同阶复杂度下，需要考虑系数、常数、低阶等。
2.3. 选择排序
选择排序也分为已排序区间和未排序区间（刚开始的已排序区间没有数据），选择排序每趟都会从未排序区间中找到最小的值（从小到大排序的话）放到已排序区间的末尾。
![]()
2.3.1. 实现
/**
* 选择排序：
* 选择排序将待排序序列分成未排序区和已排序区；
* 第一趟排序的时候整个待排序序列是未排序区；
* 每一趟排序其实就是从未排序区选择一个最值，放到已排序区；
* 跑 len-1 趟就好
*/
public void switchSort(int[] arr, int len) {
// len-1 趟，0-i 为已排序区
for (int i = 0; i < len-1; i++) {
int minIndex = i;
for (int j = i+1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
2.3.2. 算法分析
-
选择排序是原地排序，因为只需要用来存储最小值所处位置的额外空间和交换时所需的额外空间。
-
选择排序不是一个稳定的算法。因为选择排序是从未排序区间中找一个最小值，并且和前面的元素交换位置，这会破坏稳定性。比如 1、5、5、2 这样一组数据中，使用排序算法的话。当找到 2 为 5、5、2 当前未排序区间最小的元素时，2 会与第一个 5 交换位置，那么两个 5 的顺序就变了，就破坏了稳定性。
-
时间复杂度分析。最好、最坏、平均都是 O(n^2)，因为无论待排序数组情况怎么样，就算是已经有序了，都是需要依次遍历完未排序区间，需要比较的次数依次是 n-1、n-2，所以时间复杂度是 O(n^2)。
2.4. 归并排序（Merge Sort）
**归并排序的核心思想就是我要对一个数组进行排序：首先将数组分成前后两部分，然后对两部分分别进行排序，排序好之后再将两部分合在一起，那整个数组就是有序的了。对于分出的两部分可以采用相同的方式进行排序。**这个思想就是分治的思想，就是先将大问题分解成小的子问题来解决，子问题解决之后，大问题也就解决了。而对于子问题的求解也是一样的套路。这个套路有点类似于递归的方式，所以分治算法一般使用递归来实现。分治是一种解决问题的处理思想，而递归是一种实现它的编程方法。
2.4.1. 实现
下面使用递归的方式来实现归并排序。递归的递推公式是：merge_sort(p...r) = merge(merge_sort(p...q), merge_sort(q+1...r))，终止条件是 p>=r，不再递归下去了。整个实现过程是先调用 __mergeSort() 函数将两部分分别排好序，之后再使用数组合并的方式将两个排序好的部分进行合并。
/**
* 归并排序
*/
public void mergeSort(int[] arr, int len) {
__mergerSort(arr, 0, len-1);
}
private void __mergerSort(int[] arr, int begin, int end) {
if (begin == end){
return;
}
__mergerSort(arr, begin, (begin+end)/2);
__mergerSort(arr, (begin+end)/2 + 1, end);
merge(arr, begin, end);
return;
}
private void merge(int[] arr, int begin, int end) {
int[] copyArr = new int[end-begin+1];
System.arraycopy(arr, begin, copyArr, 0, end-begin+1);
int mid = (end - begin + 1)/2;
int i = 0; // begin - mid 的指针
int j = mid; // mid - end 的指针
int count = begin; // 合并之后数组的指针
while (i <= mid-1 && j <= end - begin) {
arr[count++] = copyArr[i] < copyArr[j] ? copyArr[i++] : copyArr[j++];
}
while (i <= mid-1) {
arr[count++] = copyArr[i++];
}
while (j <= end - begin) {
arr[count++] = copyArr[j++];
}
}
2.4.2. 算法分析
-
归并排序可以是稳定的排序算法，只要确保合并时，如果遇到两个相等值的，前半部分那个相等的值是在后半部分那个相等的值的前面即可保证是稳定的排序算法。
-
归并排序的时间复杂度为 O(nlogn)，无论是最好、最坏还是平均情况都一样。
归并的时间复杂度分析则是递归代码的时间复杂度的分析。假设求解问题 a 可以分为对 b、c 两个子问题的求解。那么问题 a 的时间是 T(a) 、求解 b、c 的时间分别是 T(b) 和 T(c)，那么 T(a) = T(b) +T(c) + K。k 等于将 b、c 两个子问题的结果合并问题 a 所消耗的时间。
套用上述的套路，假设对 n 个元素进行归并排序需要的时间是 T(n)，子问题归并排序的时间是 T(n/2)，合并操作的时间复杂度是 O(n)。所以，T(n) =2 * T(n/2) +O(n)，T(1) = C。最终得到：
T(n)= 2*T(n/2) + n
= 2*(2*T(n/4)+ n/2)+n = 2^2*T(n/4) + 2*n
= 2^2*(2*T(n/8)+n/4) + 2*n = 2^3*T(n/8) + 3*n
= ....
= 2^k*T(n/2^K) + k*n
= ....
= 2^(log_2^n)*T(1) + log_2^n*n
最终得到 ，使用大 O 时间复杂表示 T(n)=O(nlogn)。
归并排序中，无论待排数列是有序还是倒序，最终递归的层次都是到只有一个数组为主，所以归并排序跟待排序列没有什么关系，最好、最坏、平均的时间复杂度都是 O(nlogn)。
-
归并排序并不是原地排序，因为在归并排序的合并函数中，还需要额外的存储空间，这个存储空间是 O(n)。递归过程中，空间复杂度并不能像时间复杂度那样累加。因为在每次递归下去的过程中，虽然合并操作都会申请额外的内存空间，但是合并之后，这些申请的内存空间就会被释放掉。因此其实主要考虑最大问题合并时所需的空间复杂度即可，该空间复杂度为 O(n)。
2.5. 快速排序（Quick Sort）
快速排序利用的也是分治思想，核心思想是从待排数组中选择一个元素，然后将待排数组划分成两个部分：左边部分的元素都小于该元素的值，右边部分的元素都大于该元素的值，中间是该元素的值。然后对左右两个部分套用相同的处理方法，也就是将左边部分的元素再划分成左右两部分，右边部分的元素也再划分成左右两部分。以此类推，当递归到只有一个元素的时候，就说明此时数组是有序了的。
2.5.1. 实现
首先要对下标从 begin 到 end 之间的数据进行分区，可以选择 begin 到 end 之间的任意一个数据作为 pivot（分区点），一般是最后一个数据作为分区点。之后遍历 begin 到 end 之间的数据，将小于 pivot 的放在左边，大于的 pivot 的放在右边，将pivot 放在中间（位置 p）。经过这一操作之后，数组 begin 到 end 之间的数据就被分成了三个部分：begin 到 p-1、p、p+1 到 end。最后，返回 pivot 的下标。那么这个过程一般有三种方式：
-
首先说明这种方法不可取。在不考虑空间消耗的情况下，分区操作可以非常简单。使用两个临时数组 X 和 Y，遍历 begin 到 end 之间的数据，将小于 pivot 的数据都放到数组 X 中，将大于 pivot 的数据都放到数组 Y 中，最后将数组 X 拷贝到原数组中，然后再放入 pivot，最后再放入数组 Y。但是采用这种方式之后，快排就不是原地排序算法了，因此可以采用以下两种方法在原数组的基础之上完成分区操作。
-
第一种方法还是使用两个指针：i 和 j，i 和 j 一开始都放置在 begin 初。之后 j 指针开始遍历，如果 j 指针所指的元素小于等于 pivot，那么则将 j 指针的元素放到 i 指针的处，i 指针的元素放置于 j 处，然后 i 后移，j 后移。如果 j 指针所指的元素大于 pivot 那么 j 后移即可。首先个人觉得其实整个数组被分成三个区域：0-i-1 的为小于等于 pivot 的区域，i-j-1 为大于 pivot 的区域，j 之后的区域是未排序的区域。
-
第二种方法还是使用两个指针：i 和 j，i 从 begin 处开始，j 从 end 处开始。首先 j 从 end 开始往前遍历，当遇到小于 pivot 的时候停下来，然后此时 i 从 begin 开始往后遍历，当遇到大于 pivot 的时候停下来，此时交换 i 和 j 处的元素。之后 j 继续移动，重复上述过程，直至 i >= j。
在返回 pivot 的下标 q 之后，再根据分治的思想，将 begin 到 q-1 之间的数据和下标 q+1 到 end 之间的数据进行递归。这边一定要 q-1 和 q+1 而不能是 q 和 q+1 是因为：考虑数据已经有序的极端情况，一开始是对 begin 到 end；当分区之后 q 的位置还是 end 的位置，那么相当于死循环了。最终，当区间缩小至 1 时，说明所有的数据都有序了。
如果用递推公式来描述上述的过程的话，递推公式：quick_sort(begin...end) = quick_sort(begin...q-1) + quick_sort(q+1...end)，终止条件是：begin >= end。将这两个公式转化为代码之后，如下所示：
/**
* 快速排序
*/
public void quickSort(int[] arr, int len) {
__quickSort(arr, 0, len-1);
}
// 注意边界条件
private void __quickSort(int[] arr, int begin, int end) {
if (begin >= end) {
return;
}
// 一定要是 p-1！
int p = partition(arr, begin, end); // 先进行大致排序，并获取区分点
__quickSort(arr, begin, p-1);
__quickSort(arr, p+1, end);
}
private int partition(int[] arr, int begin, int end) {
int pValue = arr[end];
// 整两个指针，两个指针都从头开始
// begin --- i-1（含 i-1）：小于 pValue 的区
// i --- j-1（含 j-1）：大于 pValue 的区
// j --- end：未排序区
int i = begin;
int j = begin;
while (j <= end) {
if (arr[j] <= pValue) {
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
i++;
j++;
} else {
j++;
}
}
return i-1;
}
2.5.2. 优化
2.5.3. 算法分析
-
快排不是一个稳定的排序算法。因为分区的过程涉及到交换操作，原本在前面的元素可能会被交换到后面去。比如 6、8、7、6、3、5、9、4 这个数组中。在经过第一次分区操作之后，两个 6 的顺序就会发生改变。
-
快排是一种原地的排序算法。
-
快排的最坏时间复杂度是 O(n^2)，最好时间复杂度是O(nlogn)，平均时间复杂度是 O(nlogn)。
快排也是使用递归来实现，那么递归代码的时间复杂度处理方式和前面类似。
快排的时间复杂度取决于 pivot 的选择，通过合理地选择 pivot 来使得算法的时间复杂度尽可能不出现 O(n^2) 的情况。
-
假设每次分区操作都可以把数组分成大小接近相等的两个小区间，那么快排的时间复杂度和归并排序一样，都是 O(nlogn)。
-
但是分区操作不一定都能把数组分成大小接近相等的两个小区间。极端情况如数组中的数组已经有序了，如果还是取最后一个元素作为分割点，左边区间是 n-1 个数，右边区间没有任何数。此时， T(n)=T(n-1)+n，最终时间复杂度退化为 O(n^2)。大部分情况下，采用递归树的方法可得到时间复杂度是 O(nlogn)。由于极端情况是少数，因此平均时间复杂度是 O(nlogn)。
2.5.4. VS 归并排序
首先从思想上来看：归并排序的处理过程是由下到上的，先处理子问题，然后对子问题的解再合并；而快排正好相反，处理过程是由上到下的，先分区，再处理子问题。
从性能上来看：归并是一个稳定的、时间复杂度为 O(nlogn) 的排序算法，但是归并并不是一个原地排序算法（所以归并没有快排应用广泛）。而快速排序算法时间复杂度不一定是 O(nlogn)，最坏情况下是 O(n^2)，而且不是一个稳定的算法，但是通过设计可以让快速排序成为一个原地排序算法。
2.6. 堆排序
堆是一种特殊的树。只要满足以下两个条件就是一个堆。
由于”堆是一个完全二叉树“，因此一般堆使用数组来存储，一是节省空间，二是通过数组的下标就可以找到父节点、左右子节点（数组下标最好从 1 开始，该节的代码实现都将从数组下标为 1 的地方开始）。那么，借助堆这种数据结构实现的排序被称为堆排序。堆排序是一种原地的、时间复杂度为 O(nlogn) 且不稳定的排序算法。
2.6.1. 实现
整个堆排序的实现分为建堆和排序两个步骤。
建堆
首先是将待排序数组建立成一个堆，秉着能不借助额外数组则不借助的原则，我们可以直接在原数组上直接操作。这样，建堆有两个方法：
-
第一种方法类似于上述堆的操作中“往堆中插入一个元素”的思想。刚开始的时候假设堆中只有一个元素，也就是下标为 1 的元素。然后，将下标为 2 的元素插入堆中，并对堆进行调整。以此类推，将下标从 2 到 n 的元素依次插入到堆中。这种建堆方式相当于将待排序数组分成“堆区”和“待插入堆区”。
如图所示，我们将对待排序数据 7、5、19、8、4 进行建堆（大顶堆）。可以看到初始化堆就一个元素 7。之后将指针移到下标为 2 的位置，将 5 这个元素添加到堆中并从下往上进行堆化。之后，再将指针移到下标为 3 的位置，将 19 这个元素添加到堆中并从下往上进行堆化。依次类推。![]()
-
第二种方法是将整个待排序数组都当成一个“堆”，但是这个“堆”不一定满足堆的两个条件，因此我们需要对其进行整体调整。那么，调整的时候是从数组的最后开始，依次往前调整。调整的时候，只需要调整该节点及其子树满足堆的要求，并且是从上往下的方式进行调整。由于，叶子节点没有子树，所以叶子节点没必要调整，我们只需要从第一个非叶子节点开始调整（这边的第一是从后往前数的第一个）。那么第一个非叶子节点的下标为 n/2，因此我们只需要对 n/2 到 1 的数组元素进行从上往下堆化即可（下标从 n/2 到 1 的数组元素所在节点都是非叶子节点，下标从 n/2+1 到 n 的数组元素所在节点都是叶子节点）。
如图所示，我们将对待排序数据 7、5、19、8、4、1、20、13、16 进行建堆（大顶堆）。可以看到整个过程是从 8 这个元素开始进行堆化。在对 8 进行堆化的时候，仅对 8 及其子树进行堆化。在对 5 进行堆化的时候，仅对 5 及其子树进行堆化。
![]()
我们将第二种思路实现成如下代码段所示：
public void buildHeap(int[] datas, int len) {
this.heap = datas;
this.capacity = len - 1;
this.count = len - 1;
for (int i = this.count/2; i >=1; i--) {
heapifyFromTop(i);
}
}
public void heapifyFromTop(int begin) {
while (true) {
int i = begin; // i 是节点及其左右子节点中较大值的那个节点的下标
/* 就是在节点及其左右子节点中选择一个最大的值，与节点所处的位置进行；
但是，需要注意的是假如这个值正好是节点本身，那么直接退出循环；
否则需要进行交换，然后从交换之后的节点开始继续堆化 */
if (begin * 2 <= this.count && this.heap[begin] < this.heap[2 * begin]) {
i = 2 * begin;
}
if ((2 * begin + 1) <= this.count && this.heap[i] < this.heap[2 * begin + 1]) {
i = 2 * begin + 1;
}
if (i == begin) {
break;
}
swap(begin, i);
begin = i;
}
}
★
为什么下标从 n/2 到 1 的数组元素所在节点都是非叶子节点，下标从 n/2+1 到 n 的数组元素所在节点都是叶子节点？这个算是完全二叉树的一个特性。严格的证明暂时没有，不严谨的证明还是有的。这里采用反证法，假如 n/2 + 1 不是叶子节点，那么它的左子节点下标应该为 n+2，但是整个完全二叉树最大的节点的下标为 n。所以 n/2 + 1 不是叶子节点不成立，即 n/2 + 1 是叶子节点。那么同理可证 n/2 + 1 到 n 也是如此。而对于下标为 n/2 的节点来说，它的左子节点有的话下标应该为 n，n 在数组中有元素，因此 n/2 有左子节点，即 n/2 不是叶子节点。同理可证 1 到 n/2 都不是叶子节点。
”
排序
建完堆（大顶堆）之后，接下去的步骤是排序。那么具体该怎么实现排序呢？
此时，我们可以发现，堆顶的元素是最大的，即数组中的第一个元素是最大的。实现排序的过程大致如下：我们把它跟最后一个元素交换，那最大元素就放到了下标为 n 的位置。此时堆顶元素不是最大，因此需要进行堆化。采用从上而下的堆化方法（参考删除堆顶元素的堆化方法），将剩下的 n-1 个数据构建成堆。最后一个数据因为已知是最大了，所以不用参与堆化了。n-1 个数据构建成堆之后，再将堆顶的元素（下标为 1 的元素）和下标为 n-1 的元素进行交换。一直重复这个过程，直至堆中只剩一个元素，此时排序工作完成。如图所示，这是整个过程的示意图。
![]()
下面将排序的过程使用 Java 实现，如下所示。那么讲建堆和排序的过程结合在一起之后就是完整的堆排序了。
public void heapSort() {
while (this.count > 1) {
swap(this.count, 1);
this.count--;
heapifyFromTop(1);
}
}
★
详细的代码看文章开头给出的 Github 地址。
”
2.6.2. 算法分析
时间复杂度
堆排序的时间复杂度是由建堆和排序两个步骤的时间复杂度叠加而成。
在采用第二方式建堆时，从粗略的角度来看，每个节点进行堆化的时间复杂度是 O(logn)，那么 n/2 个节点堆化的总时间复杂度为 O(nlogn)。但是这此时粗略的计算，更加精确的计算结果不是 O(nlogn)，而是 O(n)。
因为叶子节点不需要进行堆化，所以需要堆化的节点从倒数第二层开始。每个节点需要堆化的过程中，需要比较和交换的次数，跟这个节点的高度 k 成正比。那么所有节点的高度之和，就是所有节点堆化的时间复杂度。假设堆顶节点对应的高度为 h ，那么整个节点对应的高度如图所示（以满二叉树为例，最后一层叶子节点不考虑）。
![]()
那么将每个非叶子节点的高度求和为
求解这个公式可将两边同时乘以 2 得到 S2，
然后再减去 S1，从而就得到 S1
由于
所以最终时间复杂度为 O(2n-logn)，也就是 O(n)。
排序过程中，我们需要进行 (n-1) 次堆化，每次堆化的时间复杂度是 O(logn)，那么排序阶段的时间复杂度为 O(nlogn)。
那么，整个总的时间复杂度为 O(nlogn)。
★
不对建堆过程的时间复杂度进行精确计算，也就是建堆以 O(nlogn) 的时间复杂度算的话，那么总的时间复杂度还是 O(nlogn)。
”
稳定与否
堆排序不是稳定的排序算法。因为在排序阶段，存在将堆的最后一个节点跟堆顶点进行互换的操作，所以有可能会改变相同数据的原始相对顺序。比如下面这样一组待排序 20、16、13、13 ，在排序时，第二个 13 会跟 20 交换，从而更换了两个 13 的相对顺序。
是否原地
堆排序是原地排序算法，因为堆排序的过程中的两个步骤中都只需要极个别临时存储空间。
2.6.3. 总结
在实际开发中，为什么快速排序要比堆排序性能要好？
-
对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序
对于基于比较的排序算法来说，整个排序过程就是由比较和交换这两个操作组成。快速排序中，交换的次数不会比逆序度多。但是堆排序的过程，第一步是建堆，这个过程存在大量的比较交换操作，并且很有可能会打乱数据原有的相对先后顺序，导致原数据的有序度降低。比如，在对一组已经按从小到大的顺序排列的数据进行堆排序时，那么建堆过程会将这组数据构建成大顶堆，而这一操作将会让数据变得更加无序。而采用快速排序的方法时，只需要比较而不需要交换。
★
最直接的方式就是做个试验看一下，对交换次数进行统计。
”
-
堆排序的访问方式没有快速排序友好
快速排序来说，数据是顺序访问的。而堆排序，数据是跳着访问的。访问的数据量如何很大的话，那么堆排序可能对 CPU 缓存不太友好。
2.7. 桶排序
**桶排序的核心思想就是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。**桶内排序完成之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。一般步骤是：
![]()
2.7.1. 实现
public void buckerSort(int[] arr, int len, int bucketCount) {
// 确定数据的范围
int minVal = arr[0];
int maxVal = arr[0];
for (int i = 1; i < len; ++i) {
if (arr[i] < minVal) {
minVal = arr[i];
} else if (arr[i] > maxVal){
maxVal = arr[i];
}
}
// 确认每个桶的所表示的范围
bucketCount = (maxVal - minVal + 1) < bucketCount ? (maxVal - minVal + 1) : bucketCount;
int bucketSize = (maxVal - minVal + 1) / bucketCount;
bucketCount = (maxVal - minVal + 1) % bucketCount == 0 ? bucketCount : bucketCount + 1;
int[][] buckets = new int[bucketCount][bucketSize];
int[] indexArr = new int[bucketCount]; // 数组位置记录
// 将数据依次放入桶中
for (int i = 0; i < len; i++) {
int bucketIndex = (arr[i] - minVal) / bucketSize;
if (indexArr[bucketIndex] == buckets[bucketIndex].length) {
expandCapacity(buckets, bucketIndex);
}
buckets[bucketIndex][indexArr[bucketIndex]++] = arr[i];
}
// 桶内排序
for (int i = 0; i < bucketCount; ++i) {
if (indexArr[i] != 0) {
quickSort(buckets[i], 0, indexArr[i] - 1);
}
}
// 桶内数据依次取出
int index = 0;
for (int i = 0; i < bucketCount; ++i) {
for (int j = 0; j < indexArr[i]; ++j) {
arr[index++] = buckets[i][j];
}
}
// 打印
for (int i = 0; i < len; ++i) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// 对数组进行扩容
public void expandCapacity(int[][] buckets, int bucketIndex) {
int[] newArr = new int[buckets[bucketIndex].length * 2];
System.arraycopy(buckets[bucketIndex], 0, newArr, 0, buckets[bucketIndex].length);
buckets[bucketIndex] = newArr;
}
2.7.2. 算法分析
-
最好时间复杂度为 O(n)，最坏时间复杂度为 O(nlogn)，平均时间复杂度为 O(n)。
如果要排序的数据为 n 个，把这些数据均匀地分到 m 个桶内，每个桶就有 k=n/m 个元素。每个桶使用快速排序，时间复杂度为 O(k.logk)。m 个 桶的时间复杂度就是 O(m*k*logk)，转换的时间复杂度就是 O(n*log(n/m))。当桶的数量 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 O(n)。
如果数据经过桶的划分之后，每个桶的数据很不平均，比如一个桶中包含了所有数据，那么桶排序就退化为 O(nlogn) 的排序算法了。
这边的平均时间复杂度为 O(n) 没有经过严格运算，只是采用粗略的方式得出的。因为桶排序大部分情况下，都能将数据进行大致均分，而极少情况出现所有的数据都在一个桶里。
-
非原地算法
因为桶排序的过程中，需要创建 m 个桶这个的空间复杂度就肯定不是 O(1) 了。在桶内采用快速排序的情况下，桶排序的空间复杂度应该是 O(n)。
-
桶排序的稳定与否，主要看两块：1.将数据放入桶中的时候是否按照顺序放入；2.桶内采用的排序算法。所以将数据放入桶中是按照顺序的，并且桶内也采用稳定的排序算法的话，那么整个桶排序则是稳定的。既然能稳定的话，那么一般算稳定的。
2.7.3. 总结
-
桶排序对要排序的数据的要求是非常苛刻的。
-
**桶排序适合应用在外部排序中。**比如要排序的数据有 10 GB 的订单数据，但是内存只有几百 MB，无法一次性把 10GB 的数据全都加载到内存中。这个时候，就可以先扫描 10GB 的订单数据，然后确定一下订单数据的所处的范围，比如订单的范围位于 1~10 万元之间，那么可以将所有的数据划分到 100 个桶里。再依次扫描 10GB 的订单数据，把 1~1000 元之内的订单存放到第一个桶中，1001~2000 元之内的订单数据存放到第二个桶中，每个桶对应一个文件，文件的命名按照金额范围的大小顺序编号如 00、01，即第一个桶的数据输出到文件 00 中。
理想情况下，如果订单数据是均匀分布的话，每个文件的数据大约是 100MB，依次将这些文件的数据读取到内存中，利用快排来排序，再将排序好的数据存放回文件中。最后只要按照文件顺序依次读取文件中的数据，并将这些数据写入到一个文件中，那么这个文件中的数据就是排序好了的。
但是，订单数据不一定是均匀分布的。划分之后可能还会存在比较大的文件，那就继续划分。比如订单金额在 1~1000 元之间的比较多，那就将这个区间继续划分为 10 个小区间，1~100、101~200 等等。如果划分之后还是很大，那么继续划分，直到所有的文件都能读入内存。
★
外部排序就是数据存储在磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。
”
2.8. 计数排序
计数排序跟桶排序类似，可以说计数排序其实是桶排序的一种特殊情况。**当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 K，那么就可以把数据划分到 K 个桶，每个桶内的数据值都是相同的，**从而省掉了桶内排序的时间。可以说计数排序和桶排序的区别其实也就在于桶的大小粒度不一样。
下面通过举例子的方式来看一下计数排序的过程。假设数组 A 中有 8 个数据，值在 0 到 5 之间，分别是：2、5、3、0、2、3、0、3。
-
首先使用大小为 6 的数组 C[6] 来存储每个值的个数，下标对应具体值。从而得到，C[6] 的情况为：2、0、2、3、0、1。
-
那么，值为 3 分的数据个数有 3 个，小于 3 分的数据个数有 4 个，所以值为 3 的数据在有序数组 R 中所处的位置应该是 4、5、6。为了快速计算出位置，对 C[6] 这个数组进行变化，C[k] 里存储小于等于值 k 的数据个数。变化之后的数组为 2、2、4、7、7、8。
-
之后我们从后往前依次扫描数据 A（ 从后往前是为了稳定），比如扫描到 3 的时候，从数据 C 中取出下标为 3 的值，是7（也就说到目前为止，包含自己在内，值小于等于 3 的数据个数有 7 个），那么 3 就是数组 R 中第 7 个元素，也就是下标为 6。当然 3 放入到数组 R 中后，C[3] 要减 1，变成 6，表示此时未排序的数据中小于等于 3 的数据个数有 6 个。
-
以此类推，当扫描到第 2 个值为 3 的数据的时候，就会将这个数据放入到 R 中下标为 5 的位置。当扫描完整个数组 A 后，数组 R 内的数据就是按照值从小到大的有序排列了。
2.8.1. 实现
/**
* 计数排序，暂时只能处理整数（包括整数和负数）
* @param arr
* @param len
*/
public void countingSort(int[] arr, int len) {
// 确定范围
int minVal = arr[0];
int maxVal = arr[0];
for (int i = 1; i < len; ++i) {
if (maxVal < arr[i]) {
maxVal = arr[i];
} else if (arr[i] < minVal) {
minVal = arr[i];
}
}
// 对数据进行处理
for (int i = 0; i < len; ++i) {
arr[i] = arr[i] - minVal;
}
maxVal = maxVal - minVal;
// 遍历数据数组，求得计数数组的个数
int[] count = new int[maxVal + 1];
for (int i = 0; i < len; ++i) {
count[arr[i]] ++;
}
printAll(count, maxVal + 1);
// 对计数数组进行优化
for (int i = 1; i < maxVal + 1; ++i) {
count[i] = count[i - 1] + count[i];
}
printAll(count, maxVal + 1);
// 进行排序，从后往前遍历（为了稳定）
int[] sort = new int[len];
for (int i = len - 1; i >= 0; --i) {
sort[count[arr[i]] - 1] = arr[i] + minVal;
count[arr[i]]--;
}
printAll(sort, len);
}
2.8.2. 算法分析
-
非原地算法
计数排序相当于桶排序的特例一样。计数排序需要额外的 k 个内存空间和 n 个新的内存空间存放排序之后的数组。
-
稳定算法
前面也提到了，假如采用从后往前遍历的方式话，那么是稳定算法。
-
时间复杂度
最好、最坏、平均时间复杂度都是一样，为 O(n+k)，k 为数据范围。这个从代码的实现可以看出，无论待排数组的情况怎么样，都是要循环同样的次数。
2.8.3. 总结
-
计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。
-
计数排序只能直接对非负整数进行排序，如果要排序的数据是其他类型的，需要在不改变相对大小的情况下，转化为非负整数。比如当要排序的数是精确到小数点后一位时，就需要将所有的数据的值都先乘以 10，转换为整数。再比如排序的数据中有负数时，数据的范围是[-1000,1000]，那么就需要先将每个数据加上 1000，转换为非负整数。
2.9. 基数排序
桶排序和计数排序都适合范围不是特别大的情况（请注意是范围），但是桶排序的范围可以比计数排序的范围稍微大一点。假如数据的范围很大很大，比如对手机号这种的，桶排序和技术排序显然不适合，因为需要的桶的数量也是十分巨大的。此时，可以使用基数排序。**基数排序的思想就是将要排序的数据拆分成位，然后逐位按照先后顺序进行比较。**比如手机号中就可以从后往前，先按照手机号最后一位来进行排序，之后再按照倒数第二位来进行排序，以此类推。当按照第一位重新排序之后，整个排序就算完成了。
需要注意的是**，按照每位排序的过程需要稳定的**，因为假如后一次的排序不稳定，前一次的排序结果将功亏一篑。比如，第一次对个位进行排序结果为 21、11、42、22、62，此时 21 在 22 前面；第二次对十位的排序假如是不稳定的话，22 可能跑到 21 前面去了。那么整个排序就错了，对个位的排序也就相当于白费了。
下面举个字符串的例子，整个基数排序的过程如下图所示：
![]()
2.9.1. 实现
/**
* 基数排序
* @param arr
* @param len
*/
public void radixSort(int[] arr, int len, int bitCount) {
int exp = 1;
for (int i = 0; i < bitCount; ++i) {
countingSort(arr, len, exp);
exp = exp * 10;
}
}
public int getBit(int value, int exp) {
return (value / exp) % 10;
}
/**
* 计数排序，暂时只能处理整数（包括整数和负数）
* @param arr
* @param len
*/
public void countingSort(int[] arr, int len, int exp) {
// 确定范围
int maxVal = getBit(arr[0], exp);
for (int i = 1; i < len; ++i) {
if (maxVal < getBit(arr[i], exp)) {
maxVal = getBit(arr[i], exp);
}
}
// 遍历数据数组，求得计数数组的个数
int[] count = new int[maxVal + 1];
for (int i = 0; i < len; ++i) {
count[getBit(arr[i], exp)] ++;
}
// 对计数数组进行优化
for (int i = 1; i < maxVal + 1; ++i) {
count[i] = count[i - 1] + count[i];
}
// 进行排序，从后往前遍历（为了稳定）
int[] sort = new int[len];
for (int i = len - 1; i >= 0; --i) {
sort[count[getBit(arr[i], exp)] - 1] = arr[i];
count[getBit(arr[i], exp)]--;
}
System.arraycopy(sort, 0, arr, 0, len);
printAll(sort, len);
}
2.9.2. 算法分析
-
非原地算法
是不是原地算法其实看针对每一位排序时所使用的算法。为了确保基数排序的时间复杂度以及每一位的稳定性，一般采用计数排序，计数排序是非原地算法，所以可以把基数排序当成非原地排序。
-
稳定算法
因为基数排序需要确保每一位进行排序时都是稳定的，所以整个基数排序时稳定的。
-
时间复杂度是 O(kn)，k 是数组的位数
最好、最坏、平均的时间复杂度都是 O(n)。因为无论待排数组的情况怎么样，基数排序其实都是遍历每一位，对每一位进行排序。假如每一位排序的过程中使用计数排序，时间复杂度为 O(n)。假如有 k 位的话，那么则需要 k 次桶排序或者计数排序。因此总的时间复杂度是 O(kn)，当 k 不大时，比如手机号是 11 位，那么基数排序的时间复杂度就近似于 O(n)。也可以从代码中看出。
2.9.3. 总结
-
基数排序的一个要求是排序的数据要是等长的。当不等长时候可以在前面或者后面补 0，比如字符串排序的话，就可以在后面补 0，因为 ASCII 码中所有的字母都大于 “0”，所以补 “0” 不会影响到原有的大小排序。
-
基数排序的另一个要求就是数据可以分割出独立的 “位” 来比较，而且位之间存在递进关系：如果 a 数据的高位比 b 数据大，那么剩下的低位就不用比较了。
-
除此之外，每一个位的数据范围不能太大，要能用线性排序算法来排序，否则，基数排序时间复杂度无法达到 O(n)。
3. 排序函数
几乎所有编程语言都会提供排序函数，比如 C 语言中 qsort()、C++ STL 中的 sort()/stable_sort()、Java 中的 Collections.sort()。这些排序函数，并不会只采用一种排序算法，而是多种排序算法的结合。当然主要使用的排序算法都是 O(nlogn) 的。
-
glibc 的 qsort() 排序函数。qsort() 会优先使用归并排序算法。当排序的数据量很大时，会使用快速排序。使用排序算法的时候也会进行优化，如使用 “三数取中法”、在堆上手动实现一个栈来模拟递归来解决。在快排的过程中，如果排序的区间的元素个数小于等于 4 时，则使用插入排序。而且在插入排序中还用到了哨兵机制，减少了一次判断。
★
在小规模数据面前 O(n^2) 时间复杂度的算法并不一定比 O(nlogn)的算法执行时间长。主要是因为时间复杂度会将系数和低阶去掉。
”
-
Array.sort() 排序函数，使用 TimSort 算法。TimSort 算法是一种归并算法和插入排序算法混合的排序算法。基本工作过程就是：
整个排序过程，分段选择策略可以保证 O(nlogn) 的时间复杂度。TimSort 主要利用了待排序列中可能有些片段已经基本有序的特性。之后，对于小片段采用插入算法进行合并，合并成大片段。最后，再使用归并排序的方式进行合并，从而完成排序工作。
-
扫描数组，确定其中的单调上升段和单调下降段，将严格下降段反转；
-
定义最小基本片段长度，长度不满足的单调片段通过插入排序的方式形成满足长度的单调片段（就是长度大于等于所要求的最小基本片段长度）
-
反复归并一些相邻片段，过程中避免归并长度相差很大的片段，直至整个排序完成。
4. 附加知识
4.1. 有序度、逆序度
在以从小到大为有序的情况中，有序度是数组中有序关系的元素对的个数，用数学公式表示如下所示。
如果 i < j，那么 a[i] < a[j]
比如 2、4、3、1、5、6 这组数据的有序度是 11；倒序排列的数组，有序度是 0；一个完全有序的数组，有序度为满有序度，为 n*(n-1)/2，比如1、2、3、4、5、6，有序度就是 15。
逆序度的定义正好跟有序度的定义相反
如果 i < j，那么 a[i] > a[j]
关于逆序度、有序度、满有序度满足如下公式
逆序度 = 满有序度 - 有序度
排序的过程其实就是减少逆序度，增加有序度的过程，如果待排序序列达到满有序度了，那么此时的序列就是有序了。
5. 总结
-
冒泡排序、选择排序可能就停留在理论的层面，实际开发应用中不多，但是插入排序还是挺有用的，有些排序算法优化的时候就会用到插入排序，比如在排序数据量小的时候会先选择插入排序。
-
冒泡、选择、插入三者的时间复杂度一般都是按 n^2 来算。**并且这三者都有一个共同特点，那就是都会将排序数列分成已排序和未排序两部分。**外层循环一次，其实是让有序部分增加一个，因此外层循环相当于对有序部分和未排序部分进行分割。而外层循环次数就是待排序的数据的个数；内层循环则主要负责处理未排序部分的元素。
-
快排的分区过程和分区思想其实特别好用，在解决很多非排序的问题上都会遇到。比如如何在 O(n) 的时间复杂度内查找一个 k 最值的问题（还用到分治，更多是分区这种方式）；比如将一串字符串划分成字母和数字两部分（其实就是分区，所以需要注意分区过程的应用）。以后看到类似分区什么的，可以想想快排分区过程的操作。
-
快排和归并使用都是分治的思想，都可使用递归的方式实现。只是归并是从下往上的处理过程，是先进行子问题处理，然后再合并；而快排是从上往下的处理过程，是先进行分区，而后再进行子问题处理。
-
桶排序、计数排序、基数排序的时间复杂度是线性的，所以这类排序算法叫做线性排序。之所以这能做到线性排序，主要是因为这三种算法都不是基于比较的排序算法，不涉及到元素之间的比较操作。但是这三种算法对排序的数据要求很苛刻。如果数据特征比较符合这些排序算法的要求，这些算法的复杂度可以达到 O(n)。
-
桶排序、计数排序针对范围不大的数据是可行的，它们的基本思想都是将数据划分为不同的桶来实现排序。
-
各种算法比较
| 排序算法 |
平均时间复杂度 |
最好时间复杂度 |
最坏时间复杂度 |
是否是原地排序 |
是否稳定 |
| 冒泡 |
O(n^2) |
O(n) |
O(n^2) |
√ |
√ |
| 插入 |
O(n^2) |
O(n) |
O(n^2) |
√ |
√ |
| 选择 |
O(n^2) |
O(n^2) |
O(n^2) |
√ |
× |
| 归并 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
× O(n) |
√ |
| 快排 |
O(nlogn) |
O(nlogn) |
O(n^2) |
√ |
× |
| 堆排序 |
O(nlogn) |
O(nlogn) |
O(nlogn) |
√ |
× |
| 桶排序 |
O(n) |
O(n) |
O(nlogn) |
× |
√ |
| 计数排序 |
O(n+k) |
O(n+k) |
O(n+k) |
× |
√ |
| 基数排序 |
O(kn) |
O(kn) |
O(kn) |
× |
√ |
6. 巨人的肩膀
-
极客时间，《数据结构与算法之美》，王争
-
《算法图解》
不甘于「本该如此」，「多选参数 」值得关注
![]()
