第十章 内部排序 知识点3：快速排序

对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置。 一、起泡排序 排序过程： 首先，将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上。 对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置。 重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止。

38 例 49 38 65 97 76 13 27 30 初始关键字 38 49 65 76 13 27 30 97 第一趟 38 49 65 13 27 30 76 第二趟 38 49 13 27 30 65 第三趟 13 38 13 27 30 49 第四趟 13 27 30 38 第五趟 13 27 30 第六趟 49 13 38 27 38 13 49 30 27 76 38 13 65 27 30 49 97 13 49 76 27 30 65 97 76 30 65 27 30 97 76 97

算法描述： void BubbleSort(SqList &L){ // 对顺序表L作起泡排序 for (i=L.length, change=TRUE; i>1 && change; --i) { 　change = FALSE; 　for (j=1; j<i; ++j) 　 if (L.r[j].key > L.r[j+1].key){ L.r[j]←→L.r[j+1]; change = TRUE； } }// for I } // BubbleSort

算法评价 时间复杂度 最好情况（正序） 比较次数：n-1 移动次数：0 最坏情况（逆序） 比较次数： 移动次数： T(n)=O(n²) 空间复杂度：S(n)=O(1)

二、快速排序——对起泡排序的改进 基本思想： 通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序 枢轴 ：中间分界的关键字称枢轴 排序过程：对r[s……t]中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=r[s]，x=rp.key

初始时令i=s,j=t 首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换 再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换 重复上述两步，直至i==j为止 再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止

x 例 初始关键字： 49 38 65 97 76 13 27 50 27 13 49 49 49 97 65 49 i j j i i j i j i j j i i j i j 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分别进行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序结束： 13 27 38 49 50 65 76 97

int Partition (Elem R[], int low, int high) { // 交换记录子序列R[low..high]中的记录，使枢轴记录到位，并返 //回其所在位置，此时在它之前（后）的记录均不大（小）于它 pivotkey = R[low].key; // 用子表的第一个记录作枢轴记录 while (low<high) { // 从表的两端交替地向中间扫描 while (low<high && R[high].key>=pivotkey) --high; R[low]←→R[high]; // 将比枢轴记录小的记录交换到低端 while (low<high && R[low].key<=pivotkey) ++low; R[low]←→R[high]; // 将比枢轴记录大的记录交换到高端 } return low; // 返回枢轴所在位置 } // Partition  

Pivotkey=49 例 初始关键字： 49 38 65 97 76 13 27 50 13 49 97 27 65 j i i j i j i j i j j i i j i j 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分别进行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序结束： 13 27 38 49 50 65 76 97

int Partition (Elem R[], int low, int high) { // 交换记录子序列R[low..high]中的记录，使枢轴记录到位，并返回 //其所在位置，此时 在它之前（后）的记录均不大（小）于它 R[0] = R[low]; // 用子表的第一个记录作枢轴记录 pivotkey = R[low].key; // 枢轴记录关键字 while (low<high) { // 从表的两端交替地向中间扫描 while(low<high&& R[high].key>=pivotkey) --high;

R[low] = R[high]; // 将比枢轴记录小的记录移到低端 while (low<high && R[low].key<=pivotkey) ++low; R[high] = R[low]; // 将比枢轴记录大的记录移到高端 } R[low] = R[0]; // 枢轴记录到位 return low; // 返回枢轴位置 } // Partition

R[low] = R[high]; // 将比枢轴记录小的记录移到低端 while (low<high && R[low].key<=pivotkey) ++low; R[high] = R[low]; // 将比枢轴记录大的记录移到高端 } R[low] = R[0]; // 枢轴记录到位 return low; // 返回枢轴位置 } // Partition 容易看出，调整过程中的枢轴位置并不重要，因此，为了减少记录的移动次 数，应先将枢轴记录“移出”，待求得枢轴记录应在的位置之后(此时low=high),再将枢轴记录到位。

快速排序的递归过程可用生成一棵二叉树形象地给出， 快速排序算法描述：P275 276 27 65 8 38 96 55 49 14 74 快速排序的递归过程可用生成一棵二叉树形象地给出， 效率分析 空间效率：每层递归调用时的指针和参数均要用栈来存放 理想情况：O(nlogn)，即树的高度； 最坏情况：二叉树是一个单链，为O(n2)。 待排序列对应递归调用过程的二叉树

时间效率：在n个记录的待排序列中，一次划分为O(n)，若设T(n)为对n个记录的待排序列进行快速排序所需时间。 理想情况： （每次总是选到中间值作枢轴） 每次划分，正好将分成两个等长的子序列，则 T(n))=O(nlog2n)  最坏情况： （每次总是选到最小或最大元素作枢轴）时效为O(n2)。 返回

快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取支点记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。

知识点小结 本知识点主要学习内部排序中交换排序的基本原则，详细讲解了快速排序的过程、两个实现的算法及其效率分析。