全屏显示专题章节

快速排序是对冒泡排序的一种改进,又称为分区交换排序,它是由托尼·霍尔（C.A.Hoare）提出并发展而来的。快速排序采用的是分治策略,它是目前已知的排序速度最快的一种排序方法。

由于在冒泡排序中记录的比较和交换总是在相邻的单元间进行的,记录每次交换只能向前或向后移动一个位置,故而比较和移动的总次数较多。而在快速排序中,记录的比较和交换是从两端向中间进行的,关键字较小的记录可能会一次从后面单元交换到前面去,与之类似,关键字较大的记录一次就能从前面单元交换到后面去,记录移动的距离较远,因而减小了总的比较次数和移动次数。

快速排序的基本思想是:通过一趟排序将待排序记录分区成两个独立的部分,其中一部分记录的关键字均小于等于另一部分记录的关键字,再分别对这两部分记录进行下一趟排序,最后使整个记录序列有序。

快速排序的排序过程具体如下。在待排序记录序列中任取一个记录R[i]（通常可选取第1个记录,称记录R[i]为参照记录）,以记录R[i]的关键字K_i为基准,将其他所有记录关键字与K_i进行比较,然后将小于K_i的记录排在R[i]之前,大于K_i的记录排在R[i]之后,这样就以R[i]为分界点,将待排序记录分成两部分（也称为两个子序列）,这个过程称为分区。经过一趟快速排序后,这两个部分及R[i]之间已经达到有序,如果R[i]之前的记录及R[i]之后的记录也都是有序的,则整个序列就达到了有序。继续对分区后的各子序列按上述过程进行分区和排序,这样重复下去,直到所有子序列只有一个记录为止,由于一个记录的序列当然可被视为是有序的,因而就不需要再分区了。当最后所有的子序列都只有一个记录时,整个序列也就有序了,故排序结束。

由此可知,快速排序的关键是对待排序序列进行分区,以及对分区出的各个子序列再进行分割。下面介绍一种分区的简单方法,这种方法是从序列的两端开始交替扫描各个记录,将关键字小于K_i的记录依次放到序列的前边,将关键字大于K_i的记录从序列的最末端开始,依次放置到序列的后边,直到扫描完所有的记录为止。

在对待排序序列或子序列进行一次分区时,可按如下步骤进行。首先选取待排序序列中的第一个记录,也可选取序列中的某个记录,作为分割的基准,并将该元素赋给临时变量temp。再设置两个指针i和j分别指向序列的起始与最后位置,然后反复进行如下两项操作。

（1）将j逐渐减小,并逐次比较R[j].key与temp.key,直到发现一个R[j].key＜temp.key为止,并将R[j]移到R[i]的位置上。这样就完成了第一趟快速排序。

（2）将i逐渐增大,并逐次比较R[i].key与temp.key,直到发现一个R[i].key＞temp.key为止,并将R[i]移到R[j]的位置上。

将上述两项操作交替进行,直到指针i与j指向同一个位置（即i＝j）为止,此时将temp移到R[i]的位置上。

快速排序算法描述如下。

（1）一趟快速排序算法的时间复杂度为O（n）。

①在理想情况下,每次排序时所选取的记录关键字值都是当前待排序列中的“中值”记录,那么该记录的排序终止位置应在该序列的中间,这样就把原来的子序列分解成了两个长度大致相等的更小的子序列,在这种情况下,排序的速度最快。设完成n个记录待排序列所需的比较次数为C（n）,则有:

C（n）≤n＋2C（n/2）≤2n＋4C（n/4）≤kn＋nC（1）（k是序列的分解次数）

若n为2的幂次值且每次分解都是等长的,则分解过程可用一棵满二叉树描述,分解次数等于树的深度k＝log₂n,因此有:

整个算法的时间复杂度为O（nlog₂n）。

②在极端情况下,即每次选取的“基准”都是当前分组序列中关键字的最小（或最大）的值,划分的结果是基准的前边（或右边）为空,即把原来的分组序列分解成一个空序列和一个长度为原来序列长度减1的子序列。总的比较次数达到最大值:

③一般情况下,序列中各记录关键字的分布是随机的,因而可以认为快速排序算法的平均时间复杂度为O（nlog₂n）。

实验证明,当n较大时,快速排序是目前认为的最好的一种内部排序方法。

（2）空间复杂度:由于算法需要一个栈的空间来实现递归,栈的大小取决于递归调用的深度,最多不超过n,若每次都选较大的部分进栈,处理较短的部分,则递归的深度最多不超过log₂n,所以快速排序的空间复杂度为O（log₂n）。

（3）稳定性:快速排序算法是不稳定排序。

【例9－5】　已知待排记录的关键字序列为43,28,39,76,98,69,4,51,58,28,请使用快速排序法进行排序。

对第一趟排序进行详细描述,其过程如下。

故而第一趟排序的结果为:28　2　8　39　4　43　69　98　51　58　76,该趟排序之后确定了43的位置,所有比43大的记录都在其后,比43小的数据都在其前。