9.3 快速排序在线视频

同学们，大家好

我是云南大学信息学院教师孔兵

这节课我们讨论快速排序

快速排序的基本思路是通过一趟排序

将待排序的记录分割成独立的两部分

其中一部分记录的关键字

均比另一部分记录的关键字小

一趟排序完成以后，关键字小的记录

在序列的前半部分，关键字大的记录

在序列的后半部分

随后通过递归分别对这两部分记录继续进行排序

最终达到整个序列的有序

下面通过一个例子，介绍一下一趟快速排序的过程

图1给出了待排序的序列，序列中有8个记录

存储在1至8号单元

一趟快速排序的目标就是把8个记录分成独立的两个部分

首先需要确定一个分割的割点

一般就以序列中第1个记录的关键字作为割点

比割点小的放在前半部分，比割点大的放在后半部分

确定分割点以后，把1号单元的记录存储到0号单元

如图2所示，用两个整型数low和high分别指示

要分割序列的低端和高端

初始时，low=1，high=8，1号单元的记录暂存到0号单元

可以把1号单元看做空单元，这是序列中前半部分的位置

我们从high开始

依次向前寻找一个关键字比割点小的记录

high对应的8号单元不比割点小

high—向前找前一个单元，high=7时

7号单元的关键字是27，比割点小

把关键字为27的记录移动到low对应的1号单元

结果如图3所示。high对应的7号单元移动以后

这个单元空了，这是序列后半部分的位置

下面我们从low开始

向后寻找一个关键字比割点大的记录

low=3时，对应单元的关键字是65，比49大

把65的记录移动到high对应的单元，结果如图4所示

移动以后low对应的3号单元又空了

继续从high开始向前寻找比49小的关键字，high=6的时候

关键字13小于49，移动13的记录到low对应的3号单元

结果如图5所示

相同的办法，97的记录移动到high对应的6号单元

如图6所示，我们继续从后向前找小于49的记录

没有找到，high=4的时候，low和high相等

表示对序列的分割已经结束

4号单元是割点的位置

把0号单元49的记录移动到4号单元

完成一趟快速排序，结果如图7所示

从图7中可以看到，1至8的序列被分割成了两个部分

前半部分1~3的关键字小于等于割点

后半部分5~8的关键字大于等于割点

从上述一趟快速排序的过程来看

关键的步骤是从后向前和从前向后

交替寻找小于割点的记录和大于割点的记录

找到后移动到空的单元

我们用当循环嵌套来实现这样的交替寻找

外层的循环条件是low

是说没有完全整个序列的分割就继续循环

内层的第1个当循环语句，是从high向前

寻找小于割点的记录，找到后移动到low对应的单元

第2个当循环，是从low向后

寻找大于割点的记录，找到后移动到high对应的单元

这样交替进行，直到low等于high为止

完成对序列的分割

下面看一快速排序的实现

Partition是一趟快速排序的函数

函数返回值是分割后割点所在的位置

示例中是4。涉及到的参数有三个

一个是存储待排序序列的结构体L

两个整型参数，low和high指示这趟要分割序列的低端和高端

函数中首先把low对应的记录暂存在0号单元

把该记录的关键字赋值给割点

随后进入嵌套的当循环完成序列的分割

循环结束后，把割点记录移动到割点存储的位置low

并把割点的位置作为返回值返回

快速排序的函数是QSort

函数中有三个参数，和Partition相同

函数的目的是对序列中low到high这段进行排序

如果low小high

也就是说要排序的序列中至少有2个记录

那么，首先调用刚才介绍的partition函数

对low和high这段序列进行分割

返回后把这段序列中割点的位置赋值pivotkey

接着递归调用自身

分别对low到pivotkey-1的前半段

和pivotkey+1的后半段进行快速排序

两个递归返回后，low到high这段序列就排好序了

从if语句的条件可以看出

QSort递归到low等于high时返回

这种情况序列中只有1个记录

通过QSort

可以完成对low到high这一段的快速排序

如果要对整个序列排序

调用QSort时

需要把1和L.length

作为实参传递给low和high

就可以完成对整个序列的排序

快速排序的时间复杂度是O(nlogn)

我们要注意快速排序的特点，就平均时间而言

快速排序是目前被认为最好的一种内部排序方法

但是也应该注意到

快速排序，最坏的情况下，它的时间效率很差

什么是快速排序最坏的情况？

快速排序是基于递归实现的

递归的深度是影响递归程序效率的主要因素

如果每趟快速排序分割的两个部分比较平衡

也就是两个部分记录个数差不多

快速排序有较好的时间效率

如果分的不平衡，最极端的情况

初始序列本身有序的话，选择第1个元素为割点

分割的两部分，一个记录个数是0

另外一个记录个数是n-1

并且后面的递归调用也是如此，递归深度较深

这种情况快速排序算法的效率非常差

这种情况最好的方法是直接插入排序

好同学们，这节课

我们就介绍到这儿

下次课再见