讲解（下）在线视频

现在，我们来学习第二种交换排序，快速排序

快速排序

每次选取一个关键字，作为基准

或者说，作为参照，英文是Pivot

将当前序列划分成两个连续的子序列

也就是，左子序列和右子序列

并且保证，左子序列里面所有的关键字，都小于等于基准

右子序列里面所有的关键字，都大于等于基准

然后，我们分别对左、右子序列进行快速排序

从这个步骤

我们可以看出，快速排序采用了递归的思想

既然用了递归，递归的终结条件是什么呢

当子序列的长度小于等于一

也就是说，最多包含一个元素的时候

因为，一个元素总是有序的

所以，这时候快速排序结束，这一次就不需要再进行递归了

这是它的终结条件

现在，我们通过一个具体的例子来看

这样一个待排序列，包含8个元素

有两个1

其中一个1，我们用红色来标志

我们现在对这样一个序列，进行第一趟快速排序

我们选取的基准，这里为了方便，我们选取当前序列的第1个元素，作为基准

事实上，基准的选择有很多种方法

我们这里只是为了方便，选取第1个元素作为基准

经过一趟快速排序之后

4这个基准，出现在了这个位置

我们先不管4为什么出现在这个位置

它左边的1、3、2、1，都是小于等于4的

右边的6、7、5，都是大于等于4的

这叫一趟快速排序

或者说，一趟划分

因为，左边的序列包含4个元素

所以，我们继续进行下一趟快速排序

我们依然是选取第一个元素作为基准

对1、3、2、1这个左子序列，进行快速排序

那1最终出现在这个位置

它右边的3、2、1包含3个元素

所以，继续进行下一趟快速排序

我们选取的基准

依然是第一个(3)

然后，3出现在这个位置

它左边的1、2，都是小于3的

那么，它包含2个元素

我们依然进行下一趟快速排序

选取第一个(1)，作为基准

那么，1出现在这个位置

它右边的2，仅仅包含一个元素

所以，递归结束

到现在为止

第一趟划分出来的左子序列1、3、2、1

我们排序完毕了

现在，我们对6、7、5进行快速排序

选取第一个元素(6)，作为基准

它出现在这个位置

左边的5，右边的7，长度都是1

所以，没必要再进行下一趟快速排序

最终，我们就得到了

排好序的序列

就是1、1、2、3、4、5、6、7

也就是这个序列

一共经历了5趟排序

那每一趟排序，具体发生了什么事情呢

或者说，初始序列是怎么得到这个序列的呢

现在，我们来看一趟排序

或者说，一趟划分，经历的事情

我们将i、j这两个变量，分别指向当前序列的第一个元素和最后一个元素

比如，初始序列是这样的

那i、j分别指向4和1

也就是，序列的首、尾元素

接下来，我们重复地做一些事情

我们从j向左找小于基准的

这里的p，就是基准

找到了，将它放到i的位置

然后，从i向右找大于基准的，放到j的位置

这两个步骤是对称的

不断地j向左减、i向右加，最终，i和j会重合，重合的时候怎么办呢

这就是基准应该出现在的位置

我们将基准放到i或者j的位置，就可以了

现在，我们具体来分析第一趟的过程

j从最后一个元素开始，向左去找小于基准的

1小于4，1就放到i的位置

从i开始，向右找大于基准的

这里的3不大于基准，5大于基准

放到j的位置

然后，j再向左，找小于基准的，2小于基准，放到i的位置

i向右，找大于基准的，7大于(4)，放到j的位置

然后，j向左，找小于基准的，1小于4，放到i的位置

然后，i向右，找大于基准的，6大于4，放到j的位置

然后，j向左，找小于基准的

这时候，i、j重合了，都指向6

那么，刚才那个重复的过程就要结束

我们就应该将基准4，放到i或者j的位置

这里的3，因为i向右，找大于基准的时候

3是不大于4的

所以，这里的3没有变化

最终，第一趟排序的结果，我们就得到了

基准4，出现在这个位置

它左边的，都小于等于基准

右边的，都是大于等于基准的

这是一趟快速排序，所经历的具体的过程

现在，我们给出快速排序

它的具体算法，我们要排序的序列是L

因为，我们后面会遇到递归

所以，我们得给出当前子序列的下界和上界

初始情况下

这个low，肯定是等于1的

high呢，肯定是等于n的

也就是，我们对原始给出来的、长度为n的序列，进行快速排序

如果low

我们才要继续递归

i和j分别指向low和high

它们的初值，分别指向当前子序列的下界和上界

在移动的过程当中

我们可能会覆盖掉基准

所以，我们先把基准放到0下标的位置

因为，i的初值就是low(子序列的第一个元素)

我们刚才已经约定了，每一次快速排序的时候

我们都是将当前序列的第一个元素，作为基准

就相当于把ri放到r0里面

也就是暂存基准

接下来，我们做循环

只要i和j不重合

因为，i的初值是小于j的

只要i没有被加到j的位置

因为，j一直向左减，i一直向右加，它们始终会重合的

那么，我们开始内层的循环，内层的这个while循环很简单

从j开始向左找，j--，只要r[j]大于等于基准

因为，我们是从j开始，向左找小于基准的

只要大于等于，那就继续向左找

注意，这地方还必须有一个i

有的同学说

这个外层的while循环，已经有i

为什么这里还要有i

这是因为，我们在内层的while循环里面

它的循环体是j--，有可能在执行了多次这个while循环之后

i已经等于j了

所以，必须加上这个条件

当这个while循环结束的时候

说明，找到了小于基准的那个元素

我们就应该将j指向的那个小于

基准的元素，放到r[i]的位置

紧接着的代码，是对称的

我们从i开始向右找，i++，向右找大于基准的

只要小于等于基准

我们就继续向右找

同样，它也有这个条件来限定

那么，当这个while循环结束的时候

我们应该将r[i]

放到j的位置

这跟上面的代码是对称的

这样一个while循环结束的时候

意味着i和j相等，i、j相等的时候，就是基准的所在位置

我们将r[0]里面暂存的基准，放到r[i]或者r[j]的位置

到现在为止

我们已经将下界为low

上届为high的序列，一分为二

怎么样一分为二呢

这是基准出现的位置

i和j重合

这是下界

这是上界

i左边的，都小于等于基准

i右边的，都大于等于基准

我们现在要做的事情，就是分别对

划分出来的左、右子序列

继续进行递归，就行了

那么，左子序列的下界没有变化

上界

应该是i-1

右子序列的上界没有变化

下界应该是i+1

所以大家看到，紧接着，我们对左子序列low一直到i-1，继续进行递归，自己调用自己

然后对右子序列，下界是i+1

上界是high

进行递归

也是自己调用自己

从而完成整个快速排序

那么，快速排序

它的时间复杂度是什么呢

最坏情况下

通过分析，我们可以发现

当给定的序列是逆序的时候

或者说，我们每次选的基准，都是子序列当中最大(或最小)的那个元素

这时候，快速排序会退化成我们前面讲的冒泡排序

它的时间复杂度是n^2

一般情况下

它的时间复杂度是

nlog2(n)，我们就不具体推导了

最好的情况下

空间复杂度是log2(n)

这时候，就相当于一棵完全二叉树

因为，n个结点

如果我们保证树的层次(高度)最小

那么，二叉树它的高度应该是这个量级的

最坏的情况下

n个结点

它的高度就是n

所以这时候，递归的深度是最深的

那么，所耗费的额外的存储空间，就是n

最坏的空间复杂度

就是n

这个算法它是不稳定的

因为，根据我们前面讲的

将j指向的那个元素，直接放到i的位置

将i指向的元素，直接放到j的位置

元素也是跳着移动的

它很有可能跳过与之相同的那个关键字

所以，快速排序是不稳定的

一定不能修改成稳定的