秒懂算法快速排序算法中的分治思想
讲解快速排序的分治递归算法。
快速排序是C.R.A.Hoare于1962年提出的⼀种划分交换排序，其基本思想是通过⼀趟扫描将待排序的元素分割成独⽴的三个序列：第⼀个序列中所有元素均不⼤于基准元素、第⼆个序列是基准元素、第三个序列中所有元素均⼤于基准元素。由于第⼆个序列已经处于正确位置，因此需要再按此⽅法对第⼀个序列和第三个序列分别进⾏排序，整个排序过程可以递归进⾏，最终可使整个序列变成有序序列。
01
问题分析——分与治的⽅法
(1) 分解：快速排序的分解是基于基准元素的，所以⾸先要选定⼀个元素作为基准元素，然后以选定的基准元素为标杆，将其他元素分成两部分，⼀部分不⼤于基准元素，另⼀部分⼤于基准元素。
(2) 基准元素的选取：从待排序序列中选取的基准元素是决定算法性能的关键。基准元素的选取应该遵循平衡⼦问题的原则，即使得划分后的两个⼦序列的长度尽量相同。基准元素的选择⽅法有很多种，常⽤的有以下5种。
①取第⼀个元素。即以待排序序列的⾸元素作为基准元素。
②取最后⼀个元素。即以待排序序列的尾元素作为基准元素。
③取位于中间位置的元素。即以待排序序列的中间位置的元素作为基准元素。
④ “三者取中的规则”。即在待排序序列中，将该序列的第⼀个元素、最后⼀个元素和中间位置的元素进⾏⽐较，取三者之中值作为基准元素。
⑤随机取⼀个元素作为基准元素。
(3) 治理：递归不⼤于基准元素的⼦序列，然后再递归⼤于基准元素的⼦序列，这样不⼤于基准元素的⼦序列和⼤于基准元素的⼦序列都有序了。基准元素位于正确的位置，整个序列就都有序了，完成了排序的⽬的。边界条件为⼦序列且为空或只有1个元素。
为空或只有1个元素。
02
算法设计
将待排序的n个元素放到列表lis中，⽤left和right记录⼦问题在lis中的位置及规模，基准元素记为pivot。⾸先定义⼀个partition函数完成分解任务，然后采⽤递归⽅法完成⼦问题的排序。
在划分过程中，选取待排序元素的第⼀个元素作为基准元素，然后从左向右、从右向左两个⽅向轮流出位置不正确的元素，将其交换位置。该过程⼀直持续到所有元素都⽐较结束。最后将基准元素放到正确的位置。
划分操作伪码描述如下：
基于划分的结果，快速排序递归左边的⼦序列lis［left:j-1］，递归右边的⼦序列lis［j+1:right］，伪码描述如下：
算法：quickSort(lis, left, right)
输⼊：待排序序列、⼦问题的边界 left和 right
输出：有序序列lis
ifleft< righ t:
j← partition1(lis, left, right)
quickSort(arr, left, j- 1)
quickSort(arr, j+ 1, right)
03
实例构造
给定序列23,15,10,50,93,12,2,68，采⽤快速排序⽅法将其升序排列。
(1) 初始序列，如图3-31所⽰，23为基准元素，i=0，j=8。
■图3-31划分初始状态
(2) 从左向右扫描元素：先推动i指针，后⽐较，若i指向的元素⼩于或等于基准元素，则继续推动指针、再⽐较，直到i指向的元素⽐基准元素⼤为⽌，此时i指向的元素位置不正确，应该在右⼦序列中，所以应该调⾛，如图3-32所⽰。
■图3-32i指针停⽌状态
(3) 从右向左扫描元素：先推动j指针，后⽐较，若j指向的元素⼤于基准元素，则继续推动指针、⽐较，直到j指向的元素⽐基准元素⼩或相等为⽌，此时j指向的元素位置不正确，应该在左⼦序列中，所以应该调⾛，如图3-33所⽰。
■图3-33j指针停⽌状态
(4) 交换i指向的元素和j指向的元素，如图3-34所⽰。
■图3-34元素交换后的状态
(5) 由于i<j，所以继续循环，推动i指针，直到i指向的元素⼤于基准元素；推动j指针，直到j指向的元素⼩于或等于基准元素，如图3-35所⽰。
■图3-35i指针和j指针第⼆次扫描停⽌的状态
(6) 此时i>j，跳出while(True)循环，将基准元素与j指向的元素交换位置，则j便是基准元素的位置，如图3-36所⽰。
■图3-36基准元素放到正确位置的状态
(7) 递归处理左⼦序列12,15,10，递归处理右⼦序列93,50,62,68。递归结束的时候，左右⼦序列均有序了，整个序列也都有序了，如图3-37所⽰。
■图3-37左右⼦问题递归结束的状态
实例讲解
算法设计与分析（Python版）
精彩回顾
秒懂算法
算法设计的⼀般过程
递推⽅程求解⽅法
活动安排问题贪⼼算法
哈夫曼编码贪⼼算法
Prim算法
Kruskal算法
选第⼆⼤元素的分治算法
下期预告秒懂算法
动态规划算法的基本思想
矩阵连乘问题
0-1背包问题的动态规划改进算法——跳跃点算法
⼦集树模型——0-1背包问题的回溯算法
满m叉树模型——图的m可着⾊问题的回溯算法
排列树模型——旅⾏商问题的分⽀限界法
最⼤⽹络流的增⼴路算法
蒙特卡罗算法
02
参考书籍
《算法设计与分析》
作者：王秋芬
定价：59.90元
03
精彩推荐
•
⼩程序游戏开发│猜数字⼩游戏（附源码+视频）
•
Flink编程基础│Scala编程初级实践
•
Flink编程基础│FlinkCEP编程实践
•
Flink编程基础│DataStream API编程实践
快速排序python实现
•
Flink编程基础│DataSet API编程实践
•
数据分析实战│客户价值分析
•
数据分析实战│价格预测挑战
•
数据分析实战│时间序列预测
•
数据分析实战│KaggleTitanic⽣存预测