Video在线视频

大家好

我们接下来将学习到一种

应用得非常普遍的排序算法

快速排序算法

顾名思义这个排序算法它的特点就是快

我们来看一下快速排序它的原理

快速排序算法

它是一种分而治之的解决问题的方法

那么什么叫做分而治之呢

我们来看一个例子

我们可以把要解决的问题

看成一个小老鼠吃蛋糕的问题

小老鼠一下子无法吃完整个蛋糕

于是它可以把这个蛋糕

分割成为比较小的蛋糕来吃

如果分割完之后这些蛋糕块还是太大

那么它可以继续的

对这些蛋糕块进行分割

直到它可以吃为止

当小老鼠把所有的小蛋糕块都吃完的时候

那么整个蛋糕就被全部吃完了

这样一个求解问题的过程

我们叫做分而治之的策略

也就是说把整个问题

先分解成为较小的问题

然后逐个去解决所有小的问题

最后整个大的问题也就迎刃而解了

快速排序算法

它所采用的正是这样的一种

分而治之的策略

排序的过程将按照下面的步骤来进行

首先我们在序列中选择一个数据元素

来作为支点

比如在这个例子中

我们选择60作为所谓的支点

然后我们根据支点来划分整个序列

我们会让序列中比支点小的记录

调整到支点的左侧

而那些大于等于支点的记录

调整到支点的右侧

所以这个时候支点它所处在的位置

就是它在最终排序结果中的位置

另外我们还得到了

在支点左右两侧的两个更短的子序列

接下来我们像小老鼠分蛋糕一样

对子序列继续地进行划分

比如在这个例子中

我们在左序列中选择6作为支点

然后继续对它进行划分

因为其它的元素都要大于6

所以其它的元素都调整到了6的右侧

同样的

我们在右边这个子序列中

选择73作为支点

也会继续地划分

将会得到两个更小的子序列

同时我们也确定了支点73的位置

这样的划分过程持续下去

直到无法再继续划分为止

每次划分

我们都会确定一个支点元素的最终位置

并且会得到更短的子序列

当所有的划分都结束的时候

我们就得到了一个有序的序列

下面我们来看一下

快速排序的具体代码实现

这里的Quicksort函数它有三个参数

第一个参数是存放数据元素的数组A

后面的i和j

分别表示我们需要排序的序列

在数组中的左边界和右边界

也就是说我们要对数组中

为之介于i和j之间的元素来进行排序

首先我们来看一下函数的边界情况

当右边界j小于等于左边界i的时候

那说明我们序列中的元素个数不超过1

这种情况下我们不需要再进一步地排序了

我们可以马上返回

而在一般的情况下

我们首先要在序列中

选择一个数据元素作为支点

这里我定义了一个findpivot函数

用来返回支点的位置

并且我们把支点的位置

记录在变量pivot中

然后我们把支点元素和最右端的元素

进行交换

将支点交换到序列的最右端

以方便我们对序列中的其它元素进行划分

然后我们通过自己定义的partition函数

对序列中的元素进行划分

这个函数

将会对序列中的元素的位置进行调整

并且最终会返回一个位置

这个位置左边的元素小于支点

而右边的元素要大于等于支点

我们把这个位置记录在k中

然后我们再将支点元素

交换到k号位置上面

这样一来我们就得到了两个子序列

支点左边的子序列它的元素要小于支点

而右边这个子序列里面的元素

要大于等于支点

在完成了这个序列的划分之后

我们接下来要对两个子序列

分别地递归调用qsort函数

进一步地对它们进行快速排序

其中左边的子序列的位置的区间

是从i到k-1

而右边的子序列的位置区间是从k+1到j

以上就是快速排序的递归实现过程

这里面我们还有findpivot以及partition

两个函数没有实现

后面我们将来解释它们的具体的过程

我们首先来看一下Findpivot函数的实现

Findpivot函数

它的主要作用是在序列中选择一个元素

来作为支点

一些常见的选择方法包括

选择第一个元素作为支点

或者可以选择中间的元素作为支点

当然还有其它的选择方法

我们这里面采用的是

中间元素作为支点的方法

Findpivot函数的实现其实非常简单

这个函数有三个参数

分别是数组A

以及序列的起始位置i和结束位置j

那么函数最后返回的

pivot的位置就是(i+j)/2

也就是中间位置

下面我们再来看一下

划分函数Partition的实现

这个函数对存储在数组中的序列进行划分

序列在数组中的起始位置是l

终止位置是r

支点是pivot

Partition函数

将会找到一个合适的划分位置

将序列分成两个部分

划分位置左边的所有元素都要小于支点

而在这个位置右边的所有元素

都要大于等于支点

我们从序列的两端往中间的方式

来去寻找这个划分的位置

我们知道序列的左端的位置是l

右端的位置是r

我们让l和r向中间进行移动

在移动的过程中

我们始终去保证l左侧的元素要小于支点

而r右侧的元素要大于等于支点

当l和r重合的时候

那么这个位置就是一个合理的划分位置

因为它的左侧的元素都小于支点

而右侧的要大于等于支点

下面我们来实现这样一个移动的过程

我们先移动l

实际上l未知的元素小于支点

我们就向右移动l 也就是说给l加1

比如在这个例子中 支点等于60

因为l位置上的元素它是72

是大于支点的

所以我们不能移动它

接下来我们再去移动r

只要l和r没有重叠

并且r位置的元素大于等于支点

那么我们就向左移动r

也就是说给r减1

在这个例子中r的位置的元素是60

所以向左移动

这个时候指向48

因为48小于支点 所以就停止移动

这个时候l和r都不能再移动了

l位置是一个大于支点的值

而r位置是一个小于支点的值

为了能够继续移动

这个时候我们就将l位置和r位置

这两个值进行了一个交换

接下来我们可以继续移动l和r

只要它们没有重合

我们就去循环地执行

这样的一个交替移动的过程

直到l和r是重合的

它们重合的位置也就是我们要划分的位置

这个位置左边的元素都小于支点

而右边的元素都要大于等于支点

那么回顾整个划分的过程

就是将l和r

从两端移动中间某个重合位置的过程

移动的次数是等于序列的总的长度n

所以这个划分过程

它的算法复杂度很自然的就等于θ(n)

运行的时间是和序列的长度成正比的

最后我们来分析一下

快速排序算法它的性能

我们知道

快速排序的过程它是一个递归划分的过程

每次划分最多会产生两个更小的子序列

这样的一个划分过程

也可以表示成为

像图中所展示的一棵二叉树

我们知道一次划分操作

它的代价和这个序列的总长度是成正比的

所以在这棵二叉树上面

每一层它的划分过程所消耗的时间

都是θ(n)

如果这棵二叉树它的高度是h的话

那么快速排序它的时间代价就是θ(hn)

二叉树的高度h它越小

那么快速排序消耗的时间也就越小

那么在最好的情况下

如果序列的划分它是完全均匀地对半划分

将会得到一棵非常平衡的二叉树

这棵二叉树它的高度是log n

所以这个时候快速排序的时间复杂度是

θ(n log n)

而在最糟糕的情况下

如果每次划分的时候

序列中所有的元素都大于等于支点

那么我们会得到一个非常不平衡的二叉树

这个二叉树它的高度等于n

因此 这个时候快速排序的时间复杂度

变成了θ(n2)

在平均的情况下

所有可能发生的划分它的概率是等大的

我们可以得到平均的时间复杂度

它也是θ(n log n)

快速排序算法它的效率是比较高的

可以看出它是远远地要好于简单排序算法

好的 这节课我们就讲到这里

下节课我们再见