Appearance
08 排序：如何利用合并与快排的小技巧，解决算法难题？
今天我们开始学习一个非常有用的算法技能，排序。
排序在工程应用中有非常重要的作用，比如你随意点开一个搜索引擎，通过搜索得到的结果就是经过排序处理的；你参加互联网电商的秒杀活动，用户请求到达服务器之后，服务端程序会根据请求到达的时间进行排序处理。在数据库的设计中，字段的有序性也会影响我们的查询性能。
因此，面试 中出现关于排序的算法题也就不足为奇了。但是，这里我们并不去介绍所有的排序算法，而是通过面试中最经常出现的两种排序算法进行深度展开。
合并排序
快速排序
学完本讲，你将收获相应的代码模板、排序的考点，以及排序在面试中的变化。现在，开始我们的算法旅程与探险！
合并排序
合并排序 是将一个数组里面的元素进行排序的有效手段。它应该是在读书时学习的一个非常经典的排序算法了。不过这里我们不再采用教科书上的讲解方式，而是采用与"二叉树 "进行结合的方式来学习。合并排序本质上与二叉树的后序遍历非常类似的。
如果你还能回想起来我们学习二叉树的时候，后序遍历 有个重要的特点：拿到子树的信息，利用子树的信息，整合出整棵树的信息。
如果我们把有序性 也当成信息 ，那么合并排序本质上就是一个后序遍历。这时新知识就和我们的旧知识产生了化学反应 。合并排序的思路可以用二叉树表示如下：
可以用伪代码表示如下：
java
function 后序遍历/合并排序():
sub_info = 子结构(子树/子数组)
full_info = 整合(sub_info)那么合并排序/后序遍历的考点就可以总结为以下 3 点：
如何划分子结构
获取子结构的信息
利用子结构的信息，整合出整棵树的信息
我们可以把关联信息表达如下：
那么接下来我们就从这三方面入手。并且与二叉树的后序遍历的代码对照着一起看。
在正式开始讲题目之前，我们先学习一下开闭原则。实际上，绝大部分语言在设计的时候，都是按照这个原则。比如数组的第一个元素取下标 0，那么长度为 n 的数组，就需要用开闭原则区间 [0, n) 来表示。
这样表示好处理，区间长度直接就是右边界减去左边界。比如 [0, 10) 的区间长度就是 10。但是如果使用双闭区间，比如 [0, 9]，那么求区间长度时，运行式为：9 - 0 + 1。还需要在减法的基础上加 1。
1. 划分
首先我们看一下如何划分子数组。对于二叉树而言，子树的划分是天然的，已经在数据结构里面约定好了，比如 TreeNode.left、TreeNode.right。
但是对于数组而言，在切分的时候，如果想到达最优的效率，那么将数组切为平均的两半效率应该是最高的（可以联想到二叉平衡树的效率）。为了帮助你理解，我绘制了动图演示，如下所示：
二叉树的写法如下：
java
// 二叉树的后序遍历左右子树
root.left, root.right; 可以直接通过root的结构体信息得到。合并排序的写法如下：
java
// 合并排序切分左右子数组
final int m = b + ((e-b)>>1);
数组a, [b, m) => 表示左子数组。
数组a, [m, e) => 表示右子数组。
需要通过计算得到。2. 子数组的信息
由于这里是排序，那么就分别需要对左子数组和右子数组进行排序。如果你还能想起来我们在"第 06 讲"介绍过的"二叉树的后序遍历"，那么对子数组的排序，只需要递归就可以了。
java
// 二叉树的后序遍历拿左右子树的信息
postOrder(root.left);
postOrder(root.right);合并排序则需要这样写：
java
// 合并排序去拿左右子数组的信息
merge_sort(a, b, m);
merge_sort(a, m, e);3. 信息的整合
接下来，我们需要将从子树/子数组里面拿到的信息进行加工。不同的需求会导致加工的方式也不太一样。对于合并排序而言，我们需要将两个有序的子数组，合并成一个大的有序的数组。
最后，还需要考虑一下边界：
当 b >= e，说明这个区间是一个空区间，没有必要再排序；
当 b + 1 == e，说明只有一个元素，也没有必要排序。
以上两种边界情况分别可以对应到当二叉树为空，以及二叉树只有一个结点的情况。
【代码】到这里，我们已经可以写出合并排序的代码了（解析在注释里）：
java
class Solution {
private void msort(int[] a, int b, int e, int t[]) {
// 空区间 或 只有一个元素
// 为了防止b + 1溢出，这里用b >= e先判断一下
if (b >= e || b + 1 >= e) {
return;
}
// 分成两半, 二叉树可以自动取得root.left, root.right
// 这里我们需要通过计算来得到左右子数组。
final int m = b + ((e - b) >> 1);
// 类比二叉树分别遍历左子树和右子树。
msort(a, b, m, t);
msort(a, m, e, t);
// i指向左子数组的开头，j指向右子数组的开头
// to指向要临时数组t与区间[b, e)对应的位置
int i = b;
int j = m;
int to = b;
// 将两个子数组进行合并, 注意下面是一个很重要的模板
// 这里的判断条是，只要两个子数组中还有元素
while (i < m || j < e) {
// 如果右子数组没有元素 或 左子数组开头的元素小于右子数组开头的元素
// 那么取走左子数组开头的元素
// 考点：a[i] <= a[j]这样可以保证合并排序是稳定的，不要写错!
if (j >= e || i < m && a[i] <= a[j]) {
t[to++] = a[i++];
} else {
// 否则就是取右子数组开头的元素
t[to++] = a[j++];
}
}
// 把合并的结果拷回原来的数组a[]
for (i = b; i < e; i++) {
a[i] = t[i];
}
}
public void mergeSort(int[] nums) {
// 如果传进来的数组为空
if (nums == null || nums.length == 0) {
return;
}
// t是一个临时中转的数组
int[] t = new int[nums.length];
msort(nums, 0, nums.length, t);
}
}复杂度分析：时间复杂度 O(NlgN)，空间复杂度 O(N)。
【小结】这里我们归纳一下合并排序的考点：
如何切分左右子数组；
如何进行合并，合并时注意循环的条件，以及稳定排序的写法；
开闭原则。
所以解决这道题目的考点可以总结如下：
拓展思路：如果你已经成功获得了合并排序的秘籍，那么可以进一步尝试一下解决链表的合并排序。
思考题：给定一个链表，如何排序，使其时间复杂度能够达到 O(NlogN)。空间复杂度为 O(1)。小提示：会用到合并排序，以及前面介绍的链表小技巧。
我们还注意到：排序与二叉树的后序遍历 联系在一起了。在"第 06 讲"中我们提到过，后序遍历有一个非常有趣的用法就是"项庄舞剑，意在沛公"，那么合并排序是不是也有同样的性质呢？
当然可以了，那么接下来，我们利用合并排序再玩一下这个套路。
例 1：逆序对
【题目】一个整数数组，当 a[i] > a[j]，并且 i < j 的时候，(a[i], a[j]) 构成一个逆序对。求一个数组中逆序对的数目。
输入：[1, 2, 3, 4, 0]
输出：4
解释：数字 0 会和前面的每一个数构成逆序对。一共有 4 对。所以输出 4。
【分析 】我们打算用合并排序 解决这个问题。其中，合并排序提供的信息是"有序性"，那么我们就找到了"项庄"------有序性 。而我们真正要求解的是"逆序对"，所以"沛公"也找到了。
下面我们回顾一下"第 06 讲"学习后序遍历的时候，我们总是利用左右子树的信息进行整合，进而得到"沛公"。对于合并排序而言，当得到有序的左右子数组之后，应该怎么得到逆序对信息呢？
这里我们用画图来表示一下：
当两个有序的子数组合并的时候，如果 a[i] <= a[j]，此时应该执行 t[to++] = a[i++]。那么左子数组的 [b, i)，以及右子数组 [m, j) 里面的元素肯定都在 a[i] 之前就被合并掉了。
由于 a[i] 在左子数组，所以 a[i] 与 [m, j) 这个范围里面的元素就构成逆序对。 因此，在此时可以得到的逆序对的数目需要加上 j - m。
【代码】到这里我们就一起来写一下代码吧（解析在注释里）：
java
class Solution {
private int cnt = 0;
private void msort(int[] a, int b, int e, int[] t) {
if (b >= e || b + 1 >= e) {
return;
}
final int m = b + ((e - b) >> 1);
msort(a, b, m, t);
msort(a, m, e, t);
int i = b;
int j = m;
int to = b;
while (i < m || j < e) {
if (j >= e || i < m && a[i] <= a[j]) {
t[to++] = a[i++];
cnt += j - m; // 是的，就在这里加一行代码就可以了。
} else {
t[to++] = a[j++];
}
}
for (i = b; i < e; i++) {
a[i] = t[i];
}
}
public int reversePairs(int[] nums) {
if (nums == null || nums.length <= 1) {
return 0;
}
int[] t = new int[nums.length];
cnt = 0;
msort(nums, 0, nums.length, t);
return cnt;
}
}【小结】我们再总结一下合并排序的特点和用法。关于逆序对这道题目，还可以做一个小更改：求解拿到顺序对的数目。开动你的聪明大脑想一想吧！你可以把想法写在留言区，我们一起交流。
接下来我们再从求逆序对那句关键的代码进行展开：
java
if (j >= e || i < m && a[i] <= a[j]) {
t[to++] = a[i++];
cnt += j - m; // 是的，就在这里加一行代码就可以了。
}由上述代码可以得知，这里求出来的逆序对是属于 a[i] 的，根据前面的分析，我们可以拓展出下面这道思考题。
深度扩展：给定一个数组 A[]，你能够返回一个数组 ans[]，ans[i] 存放 A[i] 的逆序对数目。如果做出来这道题目，你能想一下增加的考点和变化是什么吗？可以写在留言区哦。
接下来我们看一下广度扩展。
例 2：找出两个有序数组的中位数
【题目】给定两个有序数组，请找出这两个有序数组的中位数。
输入：A = [1, 2], B = [3, 4]
输出：(2 + 3) / 2 = 2.5
解释：当个数为奇数时，取排序之后的中间那个数。当个数为偶数时，取排序后中间两个数的平均值。
【分析 】这是一道来自百度 的面试题。解法有很多，我们重点介绍基于合并模板的解法。
通过合并排序，我们已经能够将两个有序的数组合并成一个有序的数组了。合并 是一个非常经典的模板代码 ，你一定要理解并且背下来，很多地方都会用。比如合并有序链表，合并数组。
你可能会想到直接将两个有序数组合并成一个有序的数组，再取这个有序数组的中位数。但是这样操作的话，时间复杂度就变成 O(N)，并且空间复杂度也是 O(N)。
如果在面试现场，面试官一定会问你，有没有更好的办法 ？所以我们应该有效地利用两个数组的有序性解决这道题。下面我会从简单的情况开始分析。
首先我们看一维有序数组的情况，如果我们要拿第 5 小的数。（注：第 1 小就是最小的数。）只需要将前面 4 个数扔掉，然后排在前面的数就是第 5 小的数。
那么二个有序数组应该怎么办呢？不过现在非常确定的是，我们一定会扔掉 4 个数。那么接下来，你再思考一下在两个数组 A，B 中如何扔掉这 4 个数？
- 第 1 步：要扔掉 4 个数，我们需要看一下两个数组前 2 个元素，如下图所示：
此时，我们当然不知道 K、L、V、W 这四个数之间的关系。假设 L >= W，就需要证明：当 L >= W 的时候，[V, W] 都不可能是第 5 小的数，可以扔掉。
解 ：利用反证法，假设 W 可以成为第 5 小的数。推导过程如下：
同样的方法可以证明，V 也不可能成为第 5 小的数。所以如果当 L >=W 的时候，可以把 [V, W] 扔掉，不影响去拿第 5 小的数。
- 第 2 步：当我们扔掉 2 个数之后，两个有序数组已经变成如下图所示的样子：
由于我们的目标是扔掉 4 个数，扔掉 2 个数之后，还需要再扔 2 个数。此时我们只需要比较数组开头的一个元素 K, X 的大小，谁小就把谁扔掉。这里我们假设 K 比较小。
- 第 3 步：此时还剩下 1 个数需要扔掉，那么只需要扔掉 M 和 X 中较小的就可以了。
【结论】当我们需要扔掉 k 个元素：
k 是偶数的时候，我们只需要比较 A[k/2-1] 和 B[k/2-1] 的大小，谁小就扔掉对应的 [0...k/2-1] 这一段；
k 是奇数的时候，我们只需要比较 A[k/2] 和 B[k/2] 的大小，谁小就扔掉对应的 [0...k/2] 这一段。
如前面所展示的推导过程，无论 k 是偶数还是奇数，这两种情况都可以用反证法来证明。这里我总结一下偶数的情况：
思考题：你能证明 k 为奇数的情况吗？
分析：不过由于整数在程序中的整除特性，我们可以将奇数和偶数的情况统一起来。需要扔掉 k 个数的时候，p = (k-1)/ 2，你只需要比较 A[p] 和 B[p] 的大小即可。如果 A[p] >= B[p]，那么就可以把 B[0....p] 这段都扔掉。
【代码】根据之前的思考，我们可以得到如下解法（解析在注释里）：
java
double findMedianSortedArrays(int[] A, int[] B) {
final int len = A.length + B.length;
final int alen = A.length, blen = B.length;
int i = 0, j = 0;
// 如果两个数组的总长度为0
//那么不用再找了，肯定是没有中位数的，这里直接返回一个0
if (len == 0) {
return 0;
}
// 总长度为偶数的情况：
// 如果有4个数，那么当扔掉1个数之后
// 接下来需要合并的两个数排[2,3]就是中位数
// 总长度为奇数的情况：
// 比如如果有5个数，那么当合并掉2个数之后
// 接下来的那个排[3]位的就是中位数。
// 所以这里k表示：要扔掉的数的个数
int k = (len - 1) >> 1;
while (k > 0) {
// 我们需要比较A[p]与B[p]
// 只不过当数组的起始位置是i和j的时候。
// 比较的元素就变成 A[i+p], B[j+p]
final int p = (k - 1) >> 1;
// 这时直接比较A[i + p]和B[j+p]来决定谁可以被扔掉掉
// 注意这里扔掉的时候，只需要前移p + 1即可。
if (j + p >= blen || (i + p < alen && A[i + p] < B[j + p])) {
i += p + 1;
} else {
j += p + 1;
}
k -= p + 1;
}
// 把排在前面的数取出来
double front =
(j >= blen || (i < alen && A[i] < B[j])) ? A[i++] : B[j++];
// 如果总长度为奇数，那么这个时候，front就是我们要找的中位数
if ((len & 1) == 1) {
return front;
}
// 此时总的数目为偶数，那么需要再取一个数，求平均值。
double back =
(j >= blen || (i < alen && A[i] < B[j])) ? A[i] : B[j];
return (front + back) / 2.0;
}复杂度分析：一共要合并的长度可以认为是 N/2，然后每次取一半进行合并。因此，合并次数为 O(lgN)，空间复杂度为 O(1)。
【小结】至此，我们需要总结一下这道有点数学趣味的题目（实际上只是用了一个简单的反证法）。
如果，我们再看一下合并排序的过程（这里我加了一个变量 k）：
java
int alen = A.length;
int blen = B.length;
int k = alen + blen, to = 0;
int[] t = new int[k];
while (k > 0) {
if (j >= blen || i < alen && A[i] <= B[j]) {
t[to++] = A[i];
i += 1;
} else {
t[to++] = B[j];
j += 1;
}
k -= 1;
}再看这道题的核心循环的写法：
java
int alen = A.length, blen = B.length;
int len = alen + blen;
int k = (len - 1) >> 1;
int i = 0, j = 0;
while (k > 0) {
final int p = (k - 1) >> 1;
if (j + p >= blen || (i + p < alen && A[i + p] < B[j + p])) {
i += p + 1;
} else {
j += p + 1;
}
k -= p + 1;
}我们发现，正常情况下的合并排序，就是步长 p = 0 的时候的特例。那么接下来我们归纳一下合并的用法：
那么合并模板还有没有别的用法呢？这里我给你留了两道练习题。
练习题 1：给定两个有序数组 A，B。假设 A 数组中有足够的空间，不借助外部存储空间的情况下，请将 A，B，两个数组合并至 A 数组中。
练习题 2：合并两个有序链表
如果你做完练习，应该就可以将合并模板的知识图谱补充如下了：
一个小小的合并模板可就以解决这么多问题，多积累模版可以帮助我们在面试中快速答题，希望你理解并且背下来这个模板！你自己还整理过其他的通用性较强的模板吗？可以在留言区和我分享。
快速排序
快速排序也是我们在算法书里面认识的老朋友了。不过今天我仍然不会按照书里面的套路来介绍快速排序。前面我介绍了合并排序与二叉树的后序遍历有非常类似的地方，那么快速排序又和什么遍历相似呢？
是二叉树的前序遍历！前序遍历有两个重要的特点：
拿到根结点的信息
将根结点的信息，传递给左右子树
对于排序来说，有序性就是信息。因此，我们要做的事情就是把能拿到的有序信息，传递给左子数组和右子数组。
1. 有序性的传递
对于快排而言，它传递有序性的手段就是将选择一个数 x，并且利用这个数，将数组分成三部分：
小于 x 的部分放在数组的最前面
等于 x 的部分放在数组的中间
大于 x 的部分放在数组的最后面
2. 左右子数组的处理
此时，可以把小于 x 的部分当成二叉树中的左子树，大于 x 的部分当成二叉树的右子树。等于 x 的部分当成二叉树的根结点。
那么接下来要做的事情就是像前序遍历一样，递归地处理左子数组和右子数组。
这里我们模拟一下像前序遍历一样的快速排序，演示如下动图所示：
相对于二叉树的前序遍历来说，快速排序也有它自己的特点：
根结点的处理，需要执行"三路切分"操作，将一个数组切分为三段；
左右子区间是由切分动态生成的，并不像二叉树那样由指针固定。
可以用伪代码表示如下：
java
function 前序遍历/快速排序():
获取根结点的信息
将根结点的信息传递左右子树/左右子数组那么前序遍历/快速排序的考点就可以总结为以下 3 点：
如何划分子结构
获取根结点的信息
如何将根结点的信息，传递给左右子树/左右子数组。
我们可以把前序遍历与快速排序关联信息表达如下：
那么接下来我们就从上图中展示的三个方面入手，并且与二叉树的前序遍历的代码对照着一起看。
1. 划分
首先我们看一下如何划分子数组。对于二叉树而言，子树的划分是天然的，已经在数据结构里面约定好了，比如 TreeNode.left、TreeNode.right。
但是对于数组而言，切分的时候，如果想到达最优的效率，那么将数组切为平均的两半效率应该是最高的（可以联想到二叉平衡树的效率）。但是快排不能保证选择一个数，就一定能将数组切分成为两半。
切分的结果如下：
java
利用x将数组 A[]切分为三段，[小于x的部分，等于x的部分，大于x的部分]
左子树 = [小于x的部分] = [b, l)
根结点 = [等于x的部分] = [l, i)
右 子树 = [大 于x的部分] = [i, e)2. 子数组的递归
由于这里是排序，就需要分别对左子数组和右子数组进行排序。如果你还能想起来我们之前介绍过的"二叉树的前序遍历"，那么对子数组的排序应该也只需要递归就可以了。
java
// 二叉树的前序遍历拿左右子树的信息
preOrder(root.left);
preOrder(root.right);快速排序则需要这么写：
java
// 快速排序去拿左右子数组的信息
qsort(a, b, l);
qsort(a, i, e);最后，我们还需要考虑一下边界情况：
当 b >= e 的时候，说明这个区间是一个空区间，没有必要再排序；
当 b + 1 == e 的时候，说明只有一个元素，也没有必要排序。
以上两种边界情况可以对应到当二叉树为空，以及二叉树只有一个结点的情况。
【代码】让我们一起写一下快速排序的代码吧（解析在注释里）：
java
// 交换数组中两个元素的值
void swap(int[] A, int i, int j) {
int t = A[i];
A[i] = A[j];
A[j] = t;
}
// 将数组[b, e)范围的元素进行排序
void qsort(int[] A, int b, int e) {
// 像二叉树一样，如果空树/只有一个结点，那么不需要再递归了
// 如果给定的区间段为空，或者只有一个结点。
if (b >= e || b + 1 >= e) {
return;
}
// 取数组中间的元素作为x
final int m = b + ((e - b) >> 1);
final int x = A[m];
// 三路切分,这部分代码在例 3详细介绍!
int l = b, i = b, r = e - 1;
while (i <= r) {
if (A[i] < x) {
swap(A, l++, i++);
} else if (A[i] == x) {
i++;
} else {
swap(A, r--, i);
}
}
// 像二叉树的前序遍历一样，分别遍历左子树与右子树。
qsort(A, b, l);
qsort(A, i, e);
}
// 主函数，将数组nums排序
void quickSort(int[] nums) {
if (nums == null)
return;
qsort(nums, 0, nums.length);
}复杂度分析 ：快速排序在较优情况下是 O(NlgN)，在较差情况下是 O(N^2^)。
不过，我们好像还没有详细地介绍怎么进行切分操作，也就是如何将数组切分成三部分。由于切分非常重要（在 EMC 的面试中曾经单独出现过），所以我们重点介绍一下，暂且把它叫作"三路切分"。
例 3：三路切分
【题目】给定一个只包含 [0, 1, 2] 的数组，如何只通过 swap 操作，将这个数组进行排序？
输入：[2, 1, 0]
输出：[0, 1, 2]
要求：你的时间复杂度需要是 O(N)，空间复杂度需要是 O(1)。
【分析】回想一下，我们前面学过的"三路切分"，在快速排序的时候，我们通过一个整数 x 将数组切分成小于、等于、大于三部分。分别可以映射到三个值上：
0 的部分对应到小于 x 的部分
1 的部分对应到等于 x 的部分
2 的部分对应到大于 x 的部分
问题的关键就是如何在时间复杂度 O(N)，空间复杂度 O(1) 条件下完成这个操作。我们假设数组已经被切分成 4 段，如下图所示：
对于这 4 段区间，我们需要有以下约束（注意这里都要满足开闭原则）：
[0, L) 表示全是 0 的区间
[L, i) 表示全是 1 的区间
[i, r] 表示还是未处理的数的区间
(r, N) 表示全是 2 的区间
后续所有的操作都必须满足这个性质。
初始条件：L = 0, i = 0, r = N - 1。形成的 4 个区间就是：[0, 0), [0, 0), [0, N-1], (N-1, N)，除了 [0, N-1] 非空以外，另外 3 个区间都是空集，所以满足前面对区间的约束原则。
推导：在 [i, r) 区间中的值 x 取值只可能是下面 3 种情况（x = 0, x = 1, x = 2），我们分别处理如下。
- 当 x = 0 的时候，我们想要把 0 放到 [0, L) 区间里面，也就是插入到所有的 1 的前面。
除了像插入排序一样一个一个地移动 1，还有没有更好的办法呢？
答案是，不需要一个一个移动！因为 [L, i) 区间里面全都是 1，只需要将 A[L] 与 A[i] 进行交换即可。
不过由于 A[L] 与 A[i] 交换完成之后，看起来像是一个新来的 0 插入到区间 [L, i) 的前面，[L, i) 区间整体向右平移了一样。所以需要执行 L++, i++。经此操作，变更后的区间仍然满足约束。
- 当 x = 1 的时候，就比较简单了。只需要为 1 的区间 [L, i) 向右扩展一下就可以了。
由于像 [L, i) 尾部增加了一个元素一样，所以只需要执行 i++ 就可以。区间变更后，仍然满足约束。
- 当 x = 2 的时候。首先需要执行 swap(A[i], A[r])。
但是，如此一来，(r, N) 应该把左边新来的 2 包含进去，所以还需要在这个基础上执行 r--。区间变更后，仍然满足约束。
最终状态：所有的数都被处理之后，[i, r] 区间肯定为空集。由于两边都是取闭，那么必然当 i > r 的时候，[i, r] 才是空集。原本的四个区间，变成三个区间。
[0, L) 等于 0 的区间
[L, i) 等于 1 的区间
[i, N) 等于 2 的区间。注意此时由于 i > r，实际上 i = r + 1，那么区间 (r, N) 就是 [i, N)。
由于最终状态是将一个乱序的数组切分成三部分，所以这个方法又叫三路切分。
【代码】到此为止，相信你已经可以根据思路写出代码了（解析在注释里）：
java
void swap(int[] A, int i, int j) {
int t = A[i];
A[i] = A[j];
A[j] = t;
}
void split(int[] A) {
final int N = A.length;
int i = 0, l = 0, r = N - 1;
while (i <= r) {
// case 0: 需要将0元素放到左区间。l++, i++完成[L, i)区间的平移。
if (A[i] == 0)
swap(A, l++, i++);
// case 1: 元素1直接append在[L, i)区间的后面就可以了。
else if (A[i] == 1)
i++;
// case 2: 元素2需要与A[r]交换。然后区间(r, N)向左扩张
else
swap(A, r--, i);
}
}复杂度分析：时间复杂度是 O(N)，空间复杂度是 O(1)。因此满足题目要求。
【小结】这道题目如果没有只能用 swap 操作这个限制还是很简单的，但加上这个限制之后。你就只能使用"三路切分"的绝技了。三路切分的考点可以总结如下：
由上图可以知，三路切分的考点比较单一。 这里我还给你留了一道练习题，帮你巩固下这个知识点。
练习题 3：数组中有 0 和非 0 元素，请把 0 元素移动到数组末尾。其他元素保持相对顺序不变。
三路切分不仅可以用在快速排序中，还有其他一些非常有趣的应用，让我们一起来看一下。
例 4：只出现一次的数
【题目】给定一个数组，除一个数以外，其他的数都出现了两次，请把这个数找出来。
输入：nums = [3,3,1,2,2]
输出：1
要求：时间复杂度 O(N)
【分析】对于这道题，这里我们不采用异或的做法，而是利用三路切分的方式来求解这道题，思路如下：
首先任意选择一个数 x，将数组进行"三路切分"，得到的情况可能有以下 3 种（因为其他的数都是出现了两次）。
Case 1：只出现一次的数在左边，那么左区间的长度为奇数。
Case 2：只出现一次的数在中间，那么中间的数的长度为 1。直接返回 x。
Case 3：只出现一次的数在右边，那么右区间的长度为奇数。
通过分析可知，前面 3 种情况中，只有 Case 2 得到了结果。接下来我们分别讨论 Case 1 和 Case3：在 Case 1 中，只出现 1 次的数在左区间时，只需要递归地处理左区间；在 Case 3 中，只出现 1 次的数在右区间时，只需要递归地处理右区间。
【代码】题目的思路还是相当简洁的，下面我们开始写代码吧（解析在注释里）：
java
// 辅助函数：交换数组中的两个元素
void swap(int[] A, int i, int j) {
int t = A[i];
A[i] = A[j];
A[j] = t;
}
// 三路切分
int threeSplit(int[] A, int b, int e) {
if (b >= e) {
return 0;
}
// 我们取数组中间的数
final int m = b + ((e - b) >> 1);
final int x = A[m];
// 注意我们的初始区间有四个：
// [b, l) [l, i) [i, r] (r, N)
// [小于) [等于) [未知] (大于)
int l = b;
int i = b;
int r = e - 1;
while (i <= r) {
if (A[i] < x) {
swap(A, l++, i++);
} else if (A[i] == x) {
i++;
} else {
swap(A, r--, i);
}
}
// 切分完毕之后，只有三个区间
// [b, l) [l, i) [i, N)
// 首先看中间的区间
if (i - l == 1)
return A[l];
// 再看左区间
if (((l - b) & 0x01) == 1) {
return threeSplit(A, b, l);
}
// 再看右区间
return threeSplit(A, i, e);
}
int singleNumber(int[] A) {
if (A == null || A.length <= 0) {
return 0;
}
return threeSplit(A, 0, A.length);
}复杂度分析：严格的时间复杂度计算是非常复杂的，《算法导论》中专门花了大量篇幅来分析。不过在本讲，我们可以简单地分析，每次扔掉的数组长度大概是 N/2，那么取极限累计求和，复杂度大概是 O(2N)，也就是 O(N)。而变量只用了 O(1)，如果栈也算上空间，那么大概是 O(H)。H 就是递归的深度。
【小结 】尽管与位运算相比，这种解法算不上最优，不过也不失一种有趣的解法。下面我们再深挖一下这种解法的特点，与我们以前学过的知识联动一下。
这里我们与"第 06 讲"中介绍的"二叉搜索树的查找"（练习题，你做了吗？）进行一下对比。二叉搜索树的查找代码可以写成如下（解析在注释里）：
java
TreeNode searchBST(TreeNode root, int val) {
// 首先看中间的结点
if (root == null || root.val == val) {
return root;
}
// 把右子树扔掉，只看左子树
if (root.val > val) {
return searchBST(root.left, val);
}
// 把左子树扔掉，只看右子树
return searchBST(root.right, val);
}将上述代码与我们当前这道题的代码进行比较，会发现很多有趣的地方。
java
int threeSplit(int[] A, int b, int e) {
if (b >= e) {
return 0;
}
// 这里进行三路切分....代码省略掉。
// 首先看中间的区间
if (i - l == 1)
return A[l];
// 把右边的扔掉，只看左区间
if (((l - b) & 0x01) == 1) {
return threeSplit(A, b, l);
}
// 把左边的扔掉，只看右区间
return threeSplit(A, i, e);
}为了方便你理解，我把这两部分代码的联系整理在下方的思维导图中，其中有非常有趣的联系：
可以得出结论，数组其实是另外一种形式的二叉树，只不过有时候需要我们动态地把左/右子树给切分出来，不同的切分方式，可以解决不同的问题。
练习题 4：只出现一次的数，其他的数都出现了 3 次。请你把只出现一次的数找出来。
三路切分还有其他一些有趣的应用，让我们继续前进。
例 5：第 k 小的数
【题目】给定一个数组，请找出第 k 小的数（最小的数为第 1 小）。
输入：A = [2, 4, 1, 5, 3], k = 3
输出：3
【分析】如果我们把数组排序之后，直接取 A[k-1] 的数。那么就可以得到结果。但是有没有复杂度更低一点的算法呢？
仔细观察题目的特点：可以发现题目没有要求所有的数都有序，只是要求第 k 小的数即可。
因此，这道题，应该可以用堆来解决。你能想一想吗？
我们再回顾一下前面的例 4 和例 5 两道题目。例 4 要求找出那个唯一的数。而例 5 中找到的第 k 小的数，也是唯一的。
这里我们从题目的"唯一性"这个特点着手，可以发现：在例 4 中是需要判断这个唯一的数在哪个区间，那么就把其他的区间扔掉。如果能扔掉不要的区间，然后在余下的区间上递归，那我们就可以达到 O(N) 的时间复杂度了（和例 4 一样了）。
可是怎样才能判断第 k 小的数在哪个区间呢？三路切分完毕之后，应该有三个区间，下面我们基于这三个区间分别讨论。
注意：在写代码之前，我们还是要注意一下边界。由于题目中给定的 k 的值是从 1 开始。也就是当 k = 1 时，实际上对应的是最小的数，而我们数组的下标是从 0 开始的，先执行 k -- 可以让 k 从 0 开始。（后面的 k 都是从 0 开始了！）
Case 1. 第 k 小的数在左区间，此时 k < lcnt，其中 lcnt 是左区间中数的个数。
Case 2. 第 k 小的数在中间，此时 lcnt <= k < lcnt + mcnt。其中 mcnt 是中间区间的数的个数。
Case 3. 第 k 小的数在右区间，此时 k >= lcnt + mcnt。
那么，此时条件就会变成：
k < lcnt 表示在左区间
k >= lcnt && k < lcnt + mcnt 表示在中间
k >= lcnt + mcnt 表示在右区间
【代码】有了前面的思路，那么我们一起来写一下这道题的代码（解析在注释里）：
java
void swap(int[] A, int i, int j) {
int t = A[i];
A[i] = A[j];
A[j] = t;
}
// 注意这里区间为[b, e), k也是从0开始算的
int kth(int[] A, int b, int e, int k) {
// 如果为空
if (b >= e) {
return 0;
}
// 如果只有一个元素
if (b + 1 >= e) {
return A[b];
}
// 进行三路切分
final int x = A[b + ((e - b) >> 1)];
int i = b;
int l = b;
int r = e - 1;
while (i <= r) {
if (A[i] < x)
swap(A, l++, i++);
else if (A[i] == x)
i++;
else
swap(A, r--, i);
}
// 分别拿到三段的长度
final int lcnt = l - b;
final int mcnt = i - l;
// 如果第k个数落在左区间
if (k < lcnt)
return kth(A, b, l, k);
// 如果第k个数落在右区间
if (k >= (lcnt + mcnt))
return kth(A, i, e, k - lcnt - mcnt);
// 如果第k个数落在中间，那么直接返回x
return x;
}
int kthNumber(int[] A, int n, int k) {
return kth(A, 0, n, k - 1);
}复杂度分析：时间复杂度 O(N)，严格地分析非常复杂，你可以查看《算法导论》中推导，空间复杂度 O(H)，H 是递归的深度。
【小结】如果我们将例 3 与例 5 放在一起，就可以总结出这些题的考点：
如果你已经掌握了例 5 里面的解题技巧与代码模板。那么接下来我们再进行一下深度扩展，你可以尝试思考下面这道练习题。
练习题 5：给定一个整数数组，请找出里面 k 个最小的数。
广度扩展："三路切分"本质上是将二叉树的一些思路移到数组上，那么是否可以适用到其他数据结构上呢？你可以在链表上试试，比如下面这道练习题。
练习题 6：排序一个单向链表（这里我们需要使用快速排序）
总结与延伸
在这里，我们一起学习了关于排序的两个知识点，合并排序和快速排序。我们再把介绍过的知识点进行一个汇总：
在本讲，虽然只讲了两个排序，但经过不断地浇灌，我们的知识树从萌芽逐渐长成了一棵大树。前面我们也提到过，实际上，堆在上浮或者上沉的时候，操作会与"插入排序"非常类似。由于篇幅的限制，这里我们不再去详细地挖掘插入排序了。
你可以自己思考和尝试，期待你还能发现更多排序的特点和巧妙用法，并且将它们总结下来，让你"大树"（思维导图）像花儿一样开得绚烂多姿。也欢迎你在评论区和我交流，期待看到大家的奇思妙想。
思考题
我再给你留一道思考题：给定一个链表，请使用插入排序对这个链表排序吧。
你可以把答案写在评论区，我们一起讨论。接下来请和我一起踏上更加奇妙的算法与数据结构的旅程。让我们继续前进。下一讲将介绍 09 | 二分搜索：为什么说有序皆可用二分？记得按时来探险。