9.2快速排序 1、起泡排序 ●首先将第一个记录的关键字与第二个记录的关键字进行比较, 若为逆序r1]key>r2]key,则将两个记录交换; ●然后比较第二个记录与第三个记录的关键字;依次类推,直至 第n-1个记录和第n个记录的关键字比较为止。 ●上述过程称作第一趟冒泡排序,其结果使得关键字最大的记录 被安置到最后一个记录的位置上。 ●然后进行第二趟冒泡排序,对前n-1个记录进行同样操作,其结 果是使关键字次大的记录被安置到第n-1个记录的位置上 ■■■■ ,重复上述过程,直到“在一趟排序过程中没有进行过交 换记录的操作”为止 北京邮电大学自动化学院 16
北京邮电大学自动化学院 16 ⚫ 1、起泡排序 9.2 快速排序 ⚫ 首先将第一个记录的关键字与第二个记录的关键字进行比较， 若为逆序r[1].key>r[2].key，则将两个记录交换； ⚫ 然后比较第二个记录与第三个记录的关键字；依次类推，直至 第n-1个记录和第n个记录的关键字比较为止。 ⚫ 上述过程称作第一趟冒泡排序，其结果使得关键字最大的记录 被安置到最后一个记录的位置上。 ⚫ 然后进行第二趟冒泡排序，对前n-1个记录进行同样操作，其结 果是使关键字次大的记录被安置到第n-1个记录的位置上。 ⚫ ……，重复上述过程，直到“在一趟排序过程中没有进行过交 换记录的操作”为止
1、起泡排序 例38383838131313 4949491327 2727 6565132730 3030 76132730 3838 2730 49 49 27306565 3076 76 3097 第第第第第 三四荭共 初始关键字 第趟趟 趟趟趟 北京邮电大学自动化学院
北京邮电大学自动化学院 17 例 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第三趟 38 13 27 30 49第四趟 13 27 30 38第五趟 13 27 30第六趟 38 49 76 9713 972 97 13 76 76 7627 30 13 6527 6530 65 13 13 49 4930 4927 3827 380 38 30 1、起泡排序
算法描述与分析 Ch8 4.c ChB txt ●起泡排序的效率,若初始序列为“正序”,则只需进 行一趟排序,在排序过程中进行n1次关键字间的比 较;反之,若初序列“逆序”,则需进行n-1趟排序, 需进行 ∑(-1) (n ( 2 次比较。并作等数量级的记录移动,因此,总的时间 复杂度为o(n2)。 北京邮电大学自动化学院
北京邮电大学自动化学院 18 算法描述与分析 Ch8_4.c ⚫ 起泡排序的效率，若初始序列为“正序”，则只需进 行一趟排序，在排序过程中进行n-1次关键字间的比 较；反之，若初序列“逆序”，则需进行n-1趟排序， 需进行 2 ( 1) ( 1) 2 − − = = n n i i n ⚫ 次比较。并作等数量级的记录移动，因此，总的时间 复杂度为O（n 2）
2、快速排序 ●2、快速排序 ●快速排序是对起泡排序的一种改进,其基本思想是:通过 趟排序将待排序记录分割成独立的两部分,其中一部分记录 的关键字均比另一部分记录的关键字小,则可分别对这两部 分记录进行排序,以达到整个序列有序。 假设待排序的序列为{Lrs],Lrs+们],…,Lr},首先任 意选取一个记录(通常可选第一个记录Lrs])作为枢轴(或 支点 Pivot),然后按下述原则重新排列其余记录:将所有关 键字较它小的记录都安置在它的位置之前,将所有关键字较 它大的记录都安置在它的位置之后。 北京邮电大学自动化学院 19
北京邮电大学自动化学院 19 2、快速排序 ⚫ 2、快速排序 ⚫ 快速排序是对起泡排序的一种改进，其基本思想是：通过一 趟排序将待排序记录分割成独立的两部分，其中一部分记录 的关键字均比另一部分记录的关键字小，则可分别对这两部 分记录进行排序，以达到整个序列有序。 ⚫ 假设待排序的序列为{L.r[s]，L.r[s+1]，…，L.r[t]}，首先任 意选取一个记录（通常可选第一个记录L.r[s]）作为枢轴（或 支点Pivot），然后按下述原则重新排列其余记录：将所有关 键字较它小的记录都安置在它的位置之前，将所有关键字较 它大的记录都安置在它的位置之后
快速排序 ●由此,可以该“枢轴”记录最后所落的位置最作分界线,将 序列{Ls],Ls+1],…,L.r}分割成两个子序列 Lrs],Lrs+们,…,Lri-1}和{Lr[+1],Lr[i+2],…, L.r},这个过程称作一趟快速排序。 一趟快速排序的具体做法是:对rs……中记录进行一趟快 速排序,附设两个指针|oW和high,它们的初值分别为ow和 high,设枢轴记录的关键字为 Pivotkey, 首先从high所指位置起向前搜索找到第一个关键字小于 Pivotkey的记录和枢轴记录相互交换, ●然后从low所指位置起向后搜索找到第一个关键字大于 Pivotkeyl的记录和枢轴记录相互交换做,重复这两步直至 lowshigh 北京邮电大学自动化学院
北京邮电大学自动化学院 20 ⚫ 由此，可以该“枢轴”记录最后所落的位置最作分界线，将 序列{L.r[s]，L.r[s+1]，…，L.r[t]}分割成两个子序列 {L.r[s]，L.r[s+1]，…，L.r[i-1]}和 {L.r[i+1]，L.r[i+2]，…， L.r[t]}，这个过程称作一趟快速排序。 ⚫ 一趟快速排序的具体做法是：对r[s……t]中记录进行一趟快 速排序，附设两个指针low和high，它们的初值分别为low和 high，设枢轴记录的关键字为Pivotkey， ⚫ 然后从low所指位置起向后搜索找到第一个关键字大于 Pivotkey的记录和枢轴记录相互交换做，重复这两步直至 low=high。 ⚫ 首先从high所指位置起向前搜索找到第一个关键字小于 Pivotkey的记录和枢轴记录相互交换， 快速排序