第10篇-进阶排序-归并排序与快速排序的核心思想

概述：为什么学完基础排序后一定要看归并和快速排序

上一篇我们讲了冒泡、选择、插入排序。
它们非常适合建立排序直觉，但有一个共同问题：

在数据规模变大时，效率通常不够高。

因为这几种基础排序的平均时间复杂度大多是：

O(n^2)

当数组长度变大之后，性能差距会非常明显。
这时候就必须进入真正的“进阶排序”阶段，而最值得先掌握的两种算法，就是：

• 归并排序
• 快速排序

它们之所以重要，不只是因为面试常考，更因为它们代表了两种非常经典的算法思想：

• 归并排序代表“分治 + 合并”
• 快速排序代表“分治 + 划分”

这两种思路不仅用于排序，也会反复出现在很多更复杂的问题里。

所以这篇文章的目标，不只是让你会写归并和快排，而是帮你真正理解下面几件事：

1. 什么叫分治思想
2. 归并排序为什么能稳定地做到O(n log n)
3. 快速排序为什么平均很快，但最坏会退化
4. 归并和快排的核心区别到底是什么

学完这篇，你应该能从“分治过程”的角度理解归并排序和快速排序，而不是只会背递归模板。

核心概念：什么是分治思想

归并排序和快速排序都属于分治算法。

所谓分治，可以先粗略理解成三步：

1. 分解：把大问题拆成若干个更小的同类问题
2. 解决：递归地解决这些小问题
3. 合并：把小问题的结果组合起来，得到原问题答案

这个过程可以用一句非常经典的话来概括：

大问题不好直接做，就把它拆小，先解决小问题，再拼回去。

为什么排序特别适合分治

因为排序本身具有很强的“可拆分性”。

例如一个数组：

[5, 2, 4, 7, 1, 3, 2, 6]

你可以先把左半边排好，再把右半边排好，最后再想办法合成整体有序。
或者先选一个基准值，把数组划分成左右两部分，再分别排序。

这就是归并排序和快速排序的起点。

分治和递归是什么关系

很多人会把分治和递归混为一谈。
其实可以这样理解：

• 分治是一种解决问题的思路
• 递归通常是实现分治的一种手段

也就是说：

分治是“战略”，递归是“执行方式”。

分治的本质不是“递归本身”，而是把一个难处理的大问题拆成更小、更相似的子问题。

为什么进阶排序能比基础排序更快

基础排序的共同特点是：

• 经常需要反复在同一批元素之间做大量比较
• 比较和交换大多是局部推进

所以整体复杂度容易变成：

O(n^2)

而归并排序和快速排序之所以更快，是因为它们都充分利用了“分而治之”的结构，把问题规模一层层缩小。

这类算法通常会形成这样一种过程：

如果每一层处理代价大约是O(n)，而总层数大约是：

log n

那么整体复杂度就常常会变成：

O(n log n)

这正是很多高效排序算法的核心来源。

进阶排序更快，不是因为它少做了排序，而是因为它用更高效的全局组织方式减少了低效重复工作。

模板一：归并排序的核心思想

先看归并排序。

归并排序到底在做什么

归并排序的核心思想可以概括成一句话：

先把数组不断二分，直到每一段都足够小，再把两个有序段合并成一个更大的有序段。

为什么这样能行？

因为长度为1的数组天然有序。
只要你能解决“如何把两个有序数组合并成一个有序数组”，那么整个排序就能一路递归完成。

一个直观例子

对于数组：

[5, 2, 4, 7, 1, 3, 2, 6]

归并排序会先拆分成：

[5, 2, 4, 7] 和 [1, 3, 2, 6]

再继续拆成：

[5, 2] [4, 7] [1, 3] [2, 6]

再继续拆成单个元素：

[5] [2] [4] [7] [1] [3] [2] [6]

然后开始向上合并：

[2, 5] [4, 7] [1, 3] [2, 6] -> [2, 4, 5, 7] [1, 2, 3, 6] -> [1, 2, 2, 3, 4, 5, 6, 7]

归并排序最关键的不是“拆”，而是“合”

拆分本身很简单，真正核心的是：

如何把两个已经有序的数组，高效地合并成一个新的有序数组。

这个“合并”动作，就是归并排序的灵魂。

归并排序不是直接把整个数组排好，而是先把小段排好，再不断合并成更大的有序段。

归并排序的核心操作：合并两个有序数组

假设现在有两个有序数组：

left = [2, 5, 7] right = [1, 3, 6]

怎么把它们合并成一个有序数组？

方法非常自然：

1. 用两个指针分别指向两个数组开头
2. 每次取更小的那个放进结果数组
3. 某一边用完后，把另一边剩余元素全部追加进去

合并模板

publicstaticvoidmerge(int[]nums,intleft,intmid,intright,int[]temp){inti=left;intj=mid+1;intk=0;while(i<=mid&&j<=right){if(nums[i]<=nums[j]){temp[k++]=nums[i++];}else{temp[k++]=nums[j++];}}while(i<=mid){temp[k++]=nums[i++];}while(j<=right){temp[k++]=nums[j++];}for(intp=0;p<k;p++){nums[left+p]=temp[p];}}

为什么这里写<=

这和归并排序的稳定性有关。

当左右两边元素相等时，如果你优先取左边：

if(nums[i]<=nums[j])

那么左边原本靠前的元素，合并后仍然靠前，稳定性就能保住。

这也是归并排序被称为稳定排序的重要原因。

归并排序真正的技术核心，是利用双指针把两个有序区间在线性时间内合成一个更大的有序区间。

归并排序完整模板

把拆分和合并连起来，就是完整的归并排序。

publicstaticvoidmergeSort(int[]nums){int[]temp=newint[nums.length];mergeSort(nums,0,nums.length-1,temp);}privatestaticvoidmergeSort(int[]nums,intleft,intright,int[]temp){if(left>=right){return;}intmid=left+(right-left)/2;mergeSort(nums,left,mid,temp);mergeSort(nums,mid+1,right,temp);merge(nums,left,mid,right,temp);}privatestaticvoidmerge(int[]nums,intleft,intmid,intright,int[]temp){inti=left;intj=mid+1;intk=0;while(i<=mid&&j<=right){if(nums[i]<=nums[j]){temp[k++]=nums[i++];}else{temp[k++]=nums[j++];}}while(i<=mid){temp[k++]=nums[i++];}while(j<=right){temp[k++]=nums[j++];}for(intp=0;p<k;p++){nums[left+p]=temp[p];}}

这段代码的逻辑怎么理解

整个流程可以分成三件事：

1. 递归排序左半边
2. 递归排序右半边
3. 把左右两段有序结果合并

也就是说，归并排序每一层做的事情其实非常统一。

归并排序的特点

• 时间复杂度稳定
• 稳定排序
• 思路清晰
• 需要额外辅助数组

时间复杂度：

最好 / 平均 / 最坏：O(n log n)

空间复杂度：

O(n)

归并排序的强项是稳定、规律、复杂度稳定，但代价是需要额外的线性辅助空间。

模板二：快速排序的核心思想

接下来是另一位主角：快速排序。

快速排序到底在做什么

快速排序的核心思想可以概括成一句话：

先选一个基准值，把数组划分成“左边都不大于它，右边都不小于它”的两部分，再分别排序左右两边。

和归并排序相比，它的重点不在“合并”，而在“划分”。

一个直观例子

假设数组是：

[5, 2, 7, 1, 3, 6, 4]

如果选5作为基准值，那么一次划分之后，数组会变成类似：

[2, 1, 3, 4, 5, 7, 6]

这时：

• 5左边都不大于5
• 5右边都不小于5

接着只需要递归处理左边和右边。

快速排序最关键的不是“递归”，而是“分区”

和归并排序一样，拆分思路并不难。
快排真正的核心在于：

如何围绕基准值，把数组原地划分成左右两部分。

这个动作通常叫做partition。

快速排序通过选择基准值并进行分区，让一个元素快速回到相对正确的位置，再递归整理两边。

快速排序的核心操作：分区partition

快速排序有多种分区写法，初学阶段先掌握一种稳定的版本就够了。

这里采用常见的“双指针 + 取首元素为基准”的写法。

分区过程怎么理解

假设：

nums = [5, 2, 7, 1, 3, 6, 4]

取第一个元素5作为基准值pivot。

然后：

1. 从右往左找第一个小于pivot的元素
2. 从左往右找第一个大于pivot的元素
3. 交换它们
4. 直到左右指针相遇
5. 最后把pivot放到相遇位置

分区模板

publicstaticintpartition(int[]nums,intleft,intright){intpivot=nums[left];inti=left;intj=right;while(i<j){while(i<j&&nums[j]>=pivot){j--;}while(i<j&&nums[i]<=pivot){i++;}if(i<j){inttemp=nums[i];nums[i]=nums[j];nums[j]=temp;}}nums[left]=nums[i];nums[i]=pivot;returni;}

为什么要先动右指针

在这种写法里，基准值保存在left位置。
如果先动左指针，可能会破坏最终的放置逻辑。
所以通常会先从右边找“小于基准”的元素。

分区完成后发生了什么

分区结束后，返回的下标i表示：

• 该位置已经放好了基准值
• 它左边的元素都不大于基准值
• 它右边的元素都不小于基准值

注意，这并不表示左右两边已经各自完全有序。
它只是说明：

基准值已经处在一个相对正确的位置上了。

快速排序真正强大的地方，是一次分区就能确定一个基准元素的位置，并把剩余问题拆成两个更小的子区间。

快速排序完整模板

有了分区函数之后，整体递归就很自然了。

publicstaticvoidquickSort(int[]nums){quickSort(nums,0,nums.length-1);}privatestaticvoidquickSort(int[]nums,intleft,intright){if(left>=right){return;}intpivotIndex=partition(nums,left,right);quickSort(nums,left,pivotIndex-1);quickSort(nums,pivotIndex+1,right);}privatestaticintpartition(int[]nums,intleft,intright){intpivot=nums[left];inti=left;intj=right;while(i<j){while(i<j&&nums[j]>=pivot){j--;}while(i<j&&nums[i]<=pivot){i++;}if(i<j){inttemp=nums[i];nums[i]=nums[j];nums[j]=temp;}}nums[left]=nums[i];nums[i]=pivot;returni;}

快速排序的特点

• 平均情况下非常快
• 原地排序，额外空间较少
• 不稳定排序
• 最坏情况下会退化

时间复杂度：

平均：O(n log n) 最好：O(n log n) 最坏：O(n^2)

空间复杂度：

平均递归栈：O(log n) 最坏递归栈：O(n)

快速排序依赖优秀的分区效果，在平均情况下非常高效，但如果分区极不平衡，就会明显退化。

为什么快速排序最坏会退化到O(n^2)

这是很多初学者最困惑的地方。

如果每次选择的基准值都很理想，能把数组大致平分，那么递归层数大约是：

log n

每层处理代价大约是：

O(n)

于是整体就是：

O(n log n)

但如果每次基准值都选得很差，比如总是选到当前区间的最小值或最大值，那么划分就会变成：

n - 1 和 0

也就是说：

• 第一层处理n
• 第二层处理n - 1
• 第三层处理n - 2
• …

最后总复杂度就会变成：

O(n^2)

哪些数组容易触发这种退化

如果你总是取首元素为基准，那么：

• 已经有序的数组
• 逆序数组

都比较容易让快排退化。

如何优化

常见优化思路包括：

• 随机选择基准值
• 三数取中
• 小区间切换插入排序

初学阶段先知道有这些优化方向就够了，不需要一开始就全背下来。

快速排序怕的不是递归，而是每次分区都极不平衡，因为这会让“对半分”的优势彻底消失。

归并排序和快速排序到底有什么区别

这两种算法经常一起出现，所以一定要放在一起理解。

1. 核心动作不同

• 归并排序：先递归排序两边，再合并
• 快速排序：先分区确定基准，再递归整理两边

2. 稳定性不同

• 归并排序：稳定
• 快速排序：不稳定

3. 空间使用不同

• 归并排序：通常需要额外O(n)辅助空间
• 快速排序：通常是原地排序，额外空间主要来自递归栈

4. 复杂度表现不同

• 归并排序：最好、平均、最坏都稳定在O(n log n)
• 快速排序：平均很优秀，但最坏会退化到O(n^2)

5. 工程使用上的取舍不同

• 如果你非常看重稳定性，归并排序更有优势
• 如果你更看重平均性能和原地排序，快速排序常常更受欢迎

可以先用下面这张表建立直觉：

归并排序胜在稳定和复杂度稳，快速排序胜在平均速度快和原地处理能力强。

排序过程图解：把两种分治过程真正看清楚

很多人写得出代码，却看不清过程。
可以用一个统一的视角来理解。

归并排序更像“先拆开，再拼好”

[5, 2, 4, 7, 1, 3, 2, 6] -> 拆成两半 -> 继续拆成更小的两半 -> 拆到每段长度为 1 -> 再一层层合并回去

所以归并排序的节奏是：

先递归到底，再向上合并

快速排序更像“先定中间，再分治两边”

[5, 2, 7, 1, 3, 6, 4] -> 选 5 做基准 -> 划分成 [小于等于 5] 5 [大于等于 5] -> 再分别处理左区间和右区间

所以快速排序的节奏是：

先做当前层分区，再递归两边

这就是两者在“递归展开顺序”上的一个很重要差别。

进阶排序到底适合什么场景

学到这里，你应该开始建立一个更实际的判断：

什么情况下更适合归并，什么情况下更适合快排？

归并排序更适合的场景

• 需要稳定排序
• 能接受额外辅助空间
• 需要复杂度表现稳定
• 链表排序场景中非常常见

快速排序更适合的场景

• 更关注平均运行速度
• 希望尽量原地排序
• 数据在数组中存储
• 可以通过随机化等方式降低退化风险

归并排序更偏稳健型，快速排序更偏高性能型，而两者背后的分治思想比代码本身更重要。

易错点：新手写归并和快排最容易踩的坑

1. 递归终止条件写错

无论归并还是快排，最基础的一行都是：

if(left>=right){return;}

漏掉或写错这行，递归就会失控。

2. 归并排序mid划分边界不清楚

一定要明确：

• 左半边是[left, mid]
• 右半边是[mid + 1, right]

边界一旦混乱，后面的合并一定错。

3. 归并时复制回原数组的位置错了

很多人写完temp后，不知道怎么拷回去。
正确拷贝区间应该从：

left

开始，而不是总从0开始。

4. 快排分区时左右指针移动顺序写乱

快排最容易出错的就是partition。
尤其是：

• 先动哪边
• 什么时候停
• 相遇后怎么放回基准值

这几步一乱，整个算法就错。

总结

真正该学会的，不是两段模板，而是两种分治思维。
归并排序和快速排序真正重要的，不只是会写，而是你能不能从分治的角度理解“它为什么这样拆、这样递归、这样得到最终有序结果”。
当你真正理解这两种思维后，后面的二分、递归树、分治统计、TopK、逆序对等问题都会更容易打通。