7.7 速排序★3◎4

7.7 快速排序★3◎4

　　快速排序的基本思想：快速排序是通过比较关键码、交换记录，以某个记录为界（该记录称为支点），将待排序列分成两部分。其中，一部分所有记录的关键码大于等于支点记录的关键码，另一部分所有记录的关键码小于支点记录的关键码。将待排序列按关键码以支点记录分成两部分的过程，称为一次划分。对各部分不断划分，直到整个序列按关键码有序。
　　一次划分方法
　　设1≤p<q≤n，r[p]，r[p+1]，...，r[q]为待排序列：

　　一趟快排序过程示例

　　第一次搜索交换
　　从high向前搜索小于r[0].key的记录，得到结果：

　　从low向后搜索大于r[0].key的记录，得到结果：

　　第二次搜索交换
　　从high向前搜索小于r[0].key的记录，得到结果：

　　从low向后搜索大于r[0].key的记录，得到结果：

　　第三次搜索交换
　　从high向前搜索小于r[0].key的记录，得到结果：

　　从low向后搜索大于r[0].key的记录，得到结果：

　　low=high，划分结束，填入支点记录：

27 14 38 8 49 65 96 49 55 74

　　【效率分析】
　　空间效率：快速排序是递归的，每层递归调用时的指针和参数均要用栈来存放，递归调用层次数与二叉树的深度一致。因而，存储开销在理想情况下为 ，即树的高度；在最坏情况下，即二叉树是一个单链，为O(n)。
　　时间效率：在理想情况下，每次划分正好将分成两个等长的子序列，有 。
　　最坏情况下：即每次划分，只得到一个子序列，时效为 。
　　快速排序通常被认为是同数量级O(nlog2n)的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常用“三者取中法”来选取支点记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。