快速排序那点事（中）

ゝ一世哀愁。 2022-05-30 05:39 183阅读 1赞

本文主要对[快速排序那些事（上）][Link 1]中提出的若干思考题进行解析。很多人对快速排序的基本过程了如指掌，但不一定能够很快、很清晰、很准确的考虑以下的思考题。

> 思考题：  
> （1）.为什么首先只能是j先移动？  
> （2）.i和j移动的范围在哪里？  
> （3）.如果i或者j没有找到不符合要求的值怎么处理？  
> （4）.分而治之的思想体现在哪里？  
> （5）.递归调用具体使用在哪里？有哪些注意事项？

# 关于快速排序的思考解析 #

快速排序的思想很多人都能脱口而出——分而治之，并且是通过递归调用来实现的。但是当很多人手写快速排序算法的时候，总会有不经意的错误。究其根本，是因为有些细节没有注意到。

按照文中所提思考题的顺序进行一一解析：

> **思考题（1）： 为什么首先只能是j向左移动，而i要在j后面移动？**

完成从小到大的排序，也就是将小的数通过交换放到左边，将大的数通过交换放到右边。如果只是i和j指向的数相互交换，i先移动还是j先移动都无所谓。其中有一个步骤决定了i和j移动顺序，就是i、j相遇位置的数与标准点的数交换，将标准值换到相遇的位置，形成左右两边两个阵营，便于之后的分而治之。要想和队列首位的标准值交换，那么只能是一个比标准值小的数。  
![这里写图片描述][70]

因为相遇点的数值一定是比标准值小的数，那么必须是j先移动找比标准值小的数。否则会存在i、j相遇在一个比标准值大的数。例如下面的例子，5、4、3、7、8。如果i先移动，i和j会相遇在7，这将使得7和5交换，这是不符合的分而治之的前提的。

> **思考题（2）： i和j的移动的范围在哪里？**

要考虑i和j移动范围，就要明确i和j的作用，i和j通过相向运动最终相遇，在各自向对方移动的时候，将不符合左边数小右边数大规则的数通过交换换走，最终达成相遇点左边都是比标准值小的数，相遇点右边都是比标准值大的数。基于以上相向移动和最终的结果，那么i和j只能相遇，不能互相越过，否则无法确定相遇点，没有相遇点也就无法与标准点互换。

故，为了保证①交换达成两个数据部分的可行性②最终必须相遇并停在同一点，i必须从左往右单步移动、j必须从右往左单步移动，且移动条件是`i<j`。当i=j时候即不能再移动，否则将i和j无法停在同一点。

> **思考题（3）： 如果某一个哨兵没有找到不符合要求的值怎么处理？**

考虑这个问题需要可以细化为两个问题来讨论，①i没有找到比标准值小的数；②j没有找到比标准值大的数。

关于①，回忆j先移动i而后动的模式，出现①情形，一定是j停在了一个比标准值小的数上，而i开始向j移动寻找标准值大的数。i没有寻找到这样的数来和j位置的数进行交换，于是i将一直向j移动，直到i也停在了j所在位置，此时i和j相遇在一个标准值小的位置上。思考例子5、1、2、4、3、9，j先移动并停在3，i从左往右移动没有找到比5大的数，于是也停在3上。满足i和j相遇点的数值比标准值小。

关于②，同理可得。此时i肯定是停在一个小于等于标准值的位置上，新一轮的移动中，j先出发寻找比标准值大的数，没有找到，那么j肯定也是移动直接逼近i，最终停在i所在的位置，于是i和j相遇在比标准值小的位置上，标准点与相遇点的数值交换可行。例如例子5、7、9、6、10。i停在5，j直接逼近i同时停在5，此时将队列分成两个部分，空队列和7、9、6、10。继续分而治之的思想就可以。

> **思考题（4）： 分而治之和递归调用体现在哪里？**

借用大佬博客中的图讲解分而治之和递归调用的具体情形。  
![这里写图片描述][70 1]  
在上图中，初始队列处于状态A，通过以6为基准完成一轮交换之后得到状态B，此时状态B既可以分为队列C和队列K，分别再对队列C和队列K处理。队列C通过一轮交换之后也可以分成E和H分别再进行交换处理……

我们可以发现：一个需要排序队列总是可以通过一轮交换之后形成以基准数为界的两个部分。这个两个部分如果需要排序扔可以通过一轮交换形成两个部分一直继续下去，直到数字个数小于等于1时则不需要继续交换排序。

如上所述：我们总是把一个需要排序的队列分成两个部分再去排序，这就是化整为二、分而治之的思想；在一分为二，分而治之的时候，我们总是把需要排序的队列进行同一个操作——交换式排序继续划一分为二，直到无法再一分为二，其实每次都是进行交换排序和一分为二的操作，这就是一个重复的过程，就可以通过递归调用来实现。

> **思考题（5）： 递归调用有哪些注意事项？**

思考题5中关于递归调用在哪里体现的问题已经在思考题4中一并作答。此处主要解析一下递归调用的注意事项。

递归调用最怕的就是无休无止的递归调用，永远停不下来，然后程序崩溃。所以在使用递归调用的时候，一定要写好出口。快速排序中调用的出口就是——当需要处理的数据长度`<=1`的时候就不需要再进入函数内部进行若干操作，直接返回即可。

[Link 1]: http://blog.csdn.net/loongkingwhat/article/details/79444845
[70]: /images/20220530/9d24af899ac54e8faad239fe12c37782.png
[70 1]: /images/20220530/bb56ed52819d428d9b259de7ec2525fc.png