关键词：
在之前的文章当中，我们通过海盗分金币问题详细讲解了递归方法。
我们可以认为在递归的过程当中，我们通过函数自己调用自己，将大问题转化成了小问题，因此简化了编码以及建模。今天这篇文章呢，就正式和大家聊一聊将大问题简化成小问题的分治算法的经典使用场景——排序。
排序算法
排序算法有很多，很多博文都有总结，号称有十大经典的排序算法。我们信手拈来就可以说上来很多，比如插入排序、选择排序、桶排序、希尔排序、快速排序、归并排序等等。老实讲这么多排序算法，但我们实际工作中并不会用到那么多，凡是高级语言都有自带的排序工具，我们直接调用就好。为了应付面试以及提升自己算法能力呢，用到的也就那么几种。今天我们来介绍一下利用分治思想实现的两种经典排序算法——归并排序与快速排序。
归并排序
我们先来讲归并排序，归并排序的思路其实很简单，说白了只有一句话：两个有序数组归并的复杂度是(O(n))。
我们举个例子：
a = [1, 4, 6]
b = [2, 4, 5]
c = []我们用i和j分别表示a和b两个数组的下标，c表示归并之后的数组，显然一开始的时候i, j = 0, 0。我们不停地比较a和b数组i和j位置大小关系，将小的那个数填入c。
填入一个数之后：
i = 1
j = 0
a = [1, 4, 6]
b = [2, 4, 5]
c = [1]填入两个数之后：
i = 1
j = 1
a = [1, 4, 6]
b = [2, 4, 5]
c = [1, 2]我们重复以上步骤，直到a和b数组当中所有的数都填入c数组为止，我们可以很方便地写出以上操作的代码：
def merge(a, b):
i, j = 0, 0
c = []
while i < len(a) or j < len(b):
# 判断a数组是否已经全部放入
if i == len(a):
c.append(b[j])
j += 1
continue
elif j == len(b):
c.append(a[i])
i += 1
continue
# 判断大小
if a[i] <= b[j]:
c.append(a[i])
i += 1
else:
c.append(b[j])
j += 1
return c从上面的代码我们也能看出来，这个过程虽然简单，但是写成代码非常麻烦，因为我们需要判断数组是否已经全部填入的情况。这里有一个简化代码的优化，就是在a和b两个数组当中插入一个”标兵“，这个标兵设置成正无穷大的数，这样当a数组当中其他元素都弹出之后。由于标兵大于b数组当中除了标兵之外其他所有的数，就可以保证a数组永远不会越界，如此就可以简化很多代码了（前提，a和b数组当中不存在和标兵一样大的数）。
我们来看代码：
def merge(a, b):
i, j = 0, 0
# 插入标兵
a.append(MAXINT)
b.append(MAXINT)
c = []
# 由于插入了标兵，所以长度判断的时候需要-1
while i < len(a)-1 or j < len(b)-1:
if a[i] <= b[j]:
c.append(a[i])
i += 1
else:
c.append(b[j])
j += 1
return c这里应该都没有问题，接下来的问题是我们怎么利用归并数组的操作来排序呢？
其实很简单，这也是归并排序的精髓。
我们每次将一个数组一分为二，显然，这个划分出来的数组不一定是有序的。但如果我们继续切分呢？直到数组当中只有一个元素的时候，是不是就天然有序了呢？
我们举个例子：
[4, 1, 3, 2]
/ [4, 1] [3, 2]
/ / [4] [1] [3] [2]
/ /
[1, 4] [2, 3]
/
[1, 2, 3, 4]通过上面的这个过程我们可以发现，在归并排序的时候，我们先一直往下递归切分数组，直到所有的切片当中只有一个元素天然有序。接着一层一层地归并回来，当所有元素归并结束的时候，数组就完成了排序。这也就是归并排序的全部过程。
如果还不理解，还可以参考一下下面的动图。
我们来试着用代码来实现。之前我曾经在面试的时候被要求在白板上写过归并排序，当时我用的C++觉得编码还有一定的难度。现在，当我用习惯了Python之后，我感觉编码难度降低了很多。因为Python支持许多数组相关的高级操作，比如切片，变长等等。整个归并排序的代码不超过20行，我们一起来看下代码：
def merge_sort(arr):
n = len(arr)
# 当长度小于等于1，说明天然有序
if n <= 1:
return arr
mid = n // 2
# 通过切片将数组一分为二，递归排序左边以及右边部分
L, R = merge_sort(arr[: mid]), merge_sort(arr[mid: ])
n_l, n_r = len(L), len(R)
# 数组当中插入标兵
L.append(sys.maxsize)
R.append(sys.maxsize)
new_arr = []
i, j = 0, 0
# 归并已经排好序的L和R
while i < n_l or j < n_r:
if L[i] <= R[j]:
new_arr.append(L[i])
i += 1
else:
new_arr.append(R[j])
j += 1
return new_arr你看，无论是思想还是代码实现，归并排序并不难，就算一开始不熟悉，写个两遍也一定没问题了。
理解了归并排序之后，再来学快速排序就不难了，我们一起来看快速排序的算法原理。
快速排序
快速排序同样利用了分治的思想，我们每次做一个小的操作，让数组的一部分变得有序，之后我们通过递归，将这些有序的部分组合在一起，达到整体有序。
在归并排序当中，我们划分问题的方法是横向切分，我们直接将数组一分为二，针对这两个部分分别排序。快排稍稍不同，它并不是针对数组的横向切分，而是从问题本身出发的”纵向“切分。在快速排序当中，我们解决的子问题不是对数组的一部分排序，而是提升数组的有序程度。怎么提升呢？我们在数组当中寻找一个数，作为标杆，我们利用这个标杆调整数组当中元素的顺序。将小于它的放到它的左侧，大于它的放到它的右侧。这么一个操作结束之后，可以肯定的是，这个标杆所在的位置就是排序完成之后，它应该在的位置。
我们来看个例子：
a = [8, 4, 3, 9, 10, 2, 7]
我们选择7作为标杆，一轮操作之后可以得到：
a = [2, 4, 3, 7, 9, 10, 8]
接着我们怎么做呢？很简单，我们只需要针对标杆前面以及标杆后面的部分重复上述操作即可。如果还不明白的同学可以看一下下面这张动图：
如果用C++写过快排的同学肯定对于快排的代码印象深刻，它是属于典型的原理不难，但是写起来很麻烦的算法。因为快速排序需要用到两个下标，写的时候一不小心很容易写出bug。同样，由于Python当中动态数组的支持非常好，我们可以避免使用下标来实现快排，这样代码的可读性以及编码难度都要降低很多。
多说无益，我们来看代码：
def quick_sort(arr):
n = len(arr)
# 长度小于等于1说明天然有序
if n <= 1:
return arr
# pop出最后一个元素作为标杆
mark = arr.pop()
# 用less和greater分别存储比mark小或者大的数
less, greater = [], []
for x in arr:
if x <= mark:
less.append(x)
else:
greater.append(x)
arr.append(mark)
return quick_sort(less) + [mark] + quick_sort(greater)整个代码出去注释，不到15行，我想大家应该都非常容易理解。
最后，我们来分析一下这两个算法的复杂度，为什么说这两个算法都是(nlogn)的算法呢？（不考虑快速排序最差情况）这个证明非常简单，我们放一张图大家一看就明白了：
我们在递归的过程当中，我们只遍历了一遍数组，虽然我们每一层都会讲数组拆分。但是在递归树上同一层的递归函数遍历的总数加起来应该是等于数组的总长也就是n的。
而且递归的层数是有限制的，因为我们每次都将数组一分为二。而一个数组的最小长度是1，也就是说极端情况下我们一共能有(log_2^n)层，每一层的复杂度总和是n，所以整体的复杂度是(nlogn)。
当然对于快速排序算法来说，如果数组是倒序的，我们默认取最后一个元素作为标杆的话，我们是无法切分数组的，因为除它之外所有的元素都比它大。在这种情况下算法的复杂度会退化到(n^2)。所以我们说快速排序算法最差复杂度是(O(n^2))。
到这里，关于归并排序与快速排序的算法就讲完了。这两个算法并不难，我想学过算法和数据结构的同学应该都有印象，但是在实际面试当中，真正能把代码写出来并且没有明显bug的实在是不多。我想，不论之前是否已经学会了，回顾一下都是很有必要的吧。
今天的文章就到这里，希望大家有所收获。如果喜欢本文，请顺手点个关注吧。
排序算法——归并排序与快速排序(代码片段)
首先，二者都运用了递归和分治的两种重要思想。在这里递归就不做详细介绍。分治：顾名思义，分而治之，这是在排序中我们非常常见的一种思想，同时也是在其他场景乃至日常生活的优秀解题方法。当我... 查看详情
排序算法系列：归并排序算法(代码片段)
概述上一篇我们说了一个非常简单的排序算法——选择排序。其复杂程序完全是冒泡级的，甚至比冒泡还要简单。今天要说的是一个相对比较复杂的排序算法——归并排序。复杂的原因不仅在于归并排序分成了两个部分进行... 查看详情
算法排序02——归并排序介绍及其在分治算法思想上与快排的区别（含归并代码）(代码片段)
...并排序是什么？归并排序和快速排序一样，都采用了分治算法的思想，时间复杂度都为O[nlog(n)]，但其空间复杂度更大一点，为O[log(n)],不过相对的，归并是一种稳定排序，这一点和快排是不同的。归并排序的思想流程: 先分，... 查看详情
排序算法中——归并排序和快速排序(代码片段)
冒泡排序、插入排序、选择排序这三种算法的时间复杂度都为$O(n^2)$，只适合小规模的数据。今天，我们来认识两种时间复杂度为$O(nlogn)$的排序算法——归并排序（MergeSort）和快速排序（QuickSort），他们都用到了分治思想，非常... 查看详情
分治算法之快排和归并(代码片段)
分治算法思想将大问题分为小问题，从而解决小问题，最后将结果合并。分治算法一般有三个过程：分，治，合。分对应分拆大问题，治解决小问题，合将小问题答案合并起来得出最后答案。典型的分治策略有二分，快排和归并... 查看详情
c++不知算法系列之聊聊希尔归并排序算法中的分治哲学(代码片段)
1.前言排序算法中，冒泡、插入、选择属于相类似的排序算法，这类算法的共同点：通过不停地比较，再使用交换逻辑重新确定数据的位置。希尔、归并、快速排序算法也可归为同一类，它们的共同点都是建立在分治思想之上。... 查看详情
常用排序快速排序与归并排序
❤️前言本文介绍两种基于分治思想的经典排序算法：归并排序与快速排序 查看详情
算法|分治|归并排序(代码片段)
归并排序算法是一个非常经典的分治算法，和快速排序有些类似，都是将问题分解成规模更小的子问题，分别解决。但是快速排序的子问题求解完成之后就是最优解，无需进行处理。归并算法需要对分别排序完成的子序列进行合... 查看详情
排序算法总结
...：选择最小的放在最左侧，以此类推归并排序：基于分治算法快速排序(交换排序)：基于分治算法堆排序和优先级队列，基于二叉堆计数排序：小范围内的整数超级快速桶排序基数排序-桶排序的扩展两种交换排序算法1.冒泡排序-... 查看详情
数据结构与算法--分治法归并排序(代码片段)
分治法分治法的思想是：将原问题分解成若干个规模较小但是与原问题类似的问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。分治法在每层递归时都有三个步骤：分解：将原问... 查看详情
数据结构与算法--分治法归并排序(代码片段)
分治法分治法的思想是：将原问题分解成若干个规模较小但是与原问题类似的问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。分治法在每层递归时都有三个步骤：分解：将原问... 查看详情
排序算法——归并排序与递归
基本思想分析归并排序之前。我们先来了解一下分治算法。分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题。这些子问题相互独立且与原问题性质相同。求出子问题的解。就可得到原问题的解。分治算法... 查看详情
算法快速排序与归并排序对比
算法系列博客【算法】刷题范围建议和代码规范【算法】复杂度理论(时间复杂度)【字符串】最长回文子串(蛮力算法)【字符串】最长回文子串(中心线枚举算法)【字符串】最长回文子串(动态规划算法)★【字符串】字符串查找(蛮... 查看详情
排序算法——二路归并排序
二路归并排序主要运用了“分治算法”，分治算法就是将一个大的问题划分为n个规模较小而结构相似的子问题。这些子问题解决的方法都是类似的，解决掉这些小的问题之后，归并子问题的结果，就得到了“大”问题的解。二... 查看详情
数据结构与算法之排序算法：归并排序
...序的，然后再把有序的子序列合并为整天有序序列。分治算法步骤：第一步：划分。将原问题划分为几个子问题第二步：递归求解。递归求解每个子问题第三步：合并。将求解后的子问题合并成原问题代码实现（递归）：voidmerge... 查看详情
❤️五万字《十大排序算法》动图讲解❤️(建议收藏)(代码片段)
...表画解栈画解队列画解哈希表画解二叉树画解图目录零、算法概述一、插入排序二、冒泡排序三、选择排序四、计数排序五、基数排序六、归并排序七、快速排序八、随机快速九、希尔排序十、堆堆排序 今天的内容，将... 查看详情
❤️五万字《十大排序算法》动图讲解❤️(建议收藏)(代码片段)
...表画解栈画解队列画解哈希表画解二叉树画解图目录零、算法概述一、插入排序二、冒泡排序三、选择排序四、计数排序五、基数排序六、归并排序七、快速排序八、随机快速九、希尔排序十、堆堆排序 今天的内容，将... 查看详情
排序&常用算法
...快速排序QuickSort快速排序和归并排序都使用分治法来设计算法，区别在于归并排序把数组分为两个基本等长的子数组，分别排好序之后还要进行归并(Merge)操作，而快速排序拆分子数组的时候显得更有艺术，取一个基准元素，拆... 查看详情