810.3快速排序 ★冒泡排序 必排序过程 ●将第一个记录的关键字与第二个记录的关键 字进行比较，若为逆序r[1].key>r[2]key,则 交换；然后比较第二个记录与第三个记录；依 次类推，直至第n-1个记录和第n个记录比较为 止一第一趟冒泡排序，结果关键字最大的记 录被安置在最后一个记录上 ●对前-1个记录进行第二趟冒泡排序，结果使 关键字次大的记录被安置在第-1个记录位置 ●重复上述过程，直到“在一趟排序过程中没 有进行过交换记录的操作”为止
§10.3 快速排序 冒泡排序 ❖排序过程 ⚫将第一个记录的关键字与第二个记录的关键 字进行比较，若为逆序r[1].key>r[2].key，则 交换；然后比较第二个记录与第三个记录；依 次类推，直至第n-1个记录和第n个记录比较为 止——第一趟冒泡排序，结果关键字最大的记 录被安置在最后一个记录上 ⚫对前n-1个记录进行第二趟冒泡排序，结果使 关键字次大的记录被安置在第n-1个记录位置 ⚫重复上述过程，直到“在一趟排序过程中没 有进行过交换记录的操作”为止
38 38 38 38 例 13 13 13 49 49 49 13 27 27 27 65 65 13 27 30 30 30 713 13 27 30 38 38 27 30 49 49 30 65 65 76 76 97 97 第二趟 第三趟 初始关键字 第一趟 第四趟 第五趟 第六趟
例 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 9727 9730 97 13 76 76 7627 30 13 6527 6530 65 13 13 49 4930 4927 3827 3830 38 初始关键字 第一趟
必算法评价 ●时间复杂度 ◆最好情况（正序） 章比较次数：n-1 卒移动次数：0 ◆最坏情况 (逆序) 章比较次数： ∑n-)= (n2-n) 拿移动次数： T(n)=0(n) ●空间复杂度：S(门)=O(1)
❖算法评价 ⚫时间复杂度 ◆最好情况（正序） 比较次数：n-1 移动次数：0 ◆最坏情况（逆序） 比较次数： ( ) 2 1 ( ) 2 1 1 n i n n n i − = − − = 移动次数： ⚫空间复杂度：S(n)=O(1) T(n)=O(n²)
快速排序 基本思想：通过一趟排序，将待排序记录分割成独 立的两部分，其中一部分记录的关键字均比另一部分 记录的关键字小，则可分别对这两部分记录进行排序， 以达到整个序列有序 排序过程：对[S.门中记录进行一趟快速排序，附 设两个指针i和j,设枢轴记录rp=r[s],X=rp.key ●初始时令i=S,j=t ●首先从所指位置向前搜索第一个关键字小于X的 记录，并和rp交换 ·再从所指位置起向后搜索，找到第一个关键字大 于X的记录，和rp交换 ●重复上述两步，直至==j为止 ●再分别对两个子序列进行快速排序，直到每个子 序列只含有一个记录为止
快速排序 ❖基本思想：通过一趟排序，将待排序记录分割成独 立的两部分，其中一部分记录的关键字均比另一部分 记录的关键字小，则可分别对这两部分记录进行排序， 以达到整个序列有序 ❖排序过程：对r[s……t]中记录进行一趟快速排序，附 设两个指针i和j，设枢轴记录rp=r[s]，x=rp.key ⚫初始时令i=s,j=t ⚫首先从j所指位置向前搜索第一个关键字小于x的 记录，并和rp交换 ⚫再从i所指位置起向后搜索，找到第一个关键字大 于x的记录，和rp交换 ⚫重复上述两步，直至i==j为止 ⚫再分别对两个子序列进行快速排序，直到每个子 序列只含有一个记录为止