§10.3交换排序 S10.3.1冒泡排序 两两比较待排序记录的ky,发现两个记录的次序相反时即 从下向上扫推：熏气泡下沉一个位置，量轻气泡浮顶，量重气 进行交换，童到无反序的记录为止， 泡在顶时要n-1”排序 S10.3.1冒泡排序 袋结控程上泽-个位果气电沉超气 设想待排序的记录败组R[1.n垂直竖立，将每个记录R可看 作是置量为R可ky的气泡。根据轻气泡不能在重气泡之下 的原则，从下往上扫描数组R,凡扫描到违反本原则的轻气 21 泡，就使其向上“飘浮”，如此反复，重到景后任何两气泡都 是轻者在上，重者在下为止。 21 ■从下往上和从上往下交管进行，可改善性能。 初始关赞字序列：2338224523673引154Π void Bubble Sort(Sglist *L) 第一慧排序后：232238234531154167 {int j ,k,flag; 第二热排序后：222323383115414567 for心-0：j<L->-length;j+)片共有m-1慧排序 第三热排序后：222323311538414567 {flag=TRUE 第四排序后：222323153138414567 for(k=1:k<=L->length-j;k++)*一趟排序* 第五越#序后：222315233引38414567 if(LT(L->R[k+1].key,L->R[k].key)) 第六趙排序后：221523233引3841567 flag=FALSE;L->R[0]=L->R[k]; 第七热排序后：152223233138414567 L->R[k]=L->R[k+1]; ■泡排序过程 L->Rk+1-L->R0; } if (flag==TRUE)break 算法分析 §10.3.2快速排序 时间复杂度 划分交换排序，1962年由Hoare(1980图灵奖)提出。 ◆最好情况（正序）：比较次数：m-1;移动次数：0： 分治法：将原问题分解为若干个规模较小但结构与原问愿相 ◆最坏情况（逆序）： 似的子问题：递归地求解这些子问题，然后将这些子问题的 (a-i- 解组合为原问厘的解。 比较次数： 2 因此在用递归描述的分治算法的每一层递归上，都有如下三 32a-i-3na- 个步骤： 移动次数： isl 2 ①分解(divide):将原问题分解为若干个子问题，此步称 为划分： 故时间复杂度：T(n)=O(n) ®餐水8o港日性邮各子问圆者子问圆的e0 空间复杂度：Sn)=O(1) @组合(combine):将各子问题的解组合为原问愿的解。 美锌表乐为选日调用凝向。分帐和超合的流易取13 §10.3 交换排序 两两比较待排序记录的key，发现两个记录的次序相反时即 进行交换，直到无反序的记录为止。 §10.3.1 冒泡排序 „ 设想待排序的记录数组R[1..n]垂直竖立，将每个记录R[i]看 作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下 的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气 泡，就使其向上“飘浮”，如此反复，直到最后任何两气泡都 是轻者在上，重者在下为止。 „ 从下往上和从上往下交替进行，可改善性能。 14 §10.3.1 冒泡排序 ™ 从下向上扫描：重气泡下沉一个位置，最轻气泡浮顶，最重气 泡在顶时要n-1趟排序 ™ 从上向下扫描：请气泡上浮一个位置，最重气泡沉底，最轻气 泡在底时要n-1趟排序 21 8 90 1 35 90 31 26 35 18 18 90 31 26 35 [ ] [ ] 8 21 1 35 90 [ ] [ ] 冒泡排序过程 初始关键字序列: 23 38 22 45 23 67 31 15 41 第一趟排序后: 23 22 38 23 45 31 15 41 67 第二趟排序后: 22 23 23 38 31 15 41 45 67 第三趟排序后: 22 23 23 31 15 38 41 45 67 第四趟排序后: 22 23 23 15 31 38 41 45 67 第五趟排序后: 22 23 15 23 31 38 41 45 67 第六趟排序后: 22 15 23 23 31 38 41 45 67 第七趟排序后: 15 22 23 23 31 38 41 45 67 void Bubble_Sort(Sqlist *L) { int j ,k , flag ; for (j=0; j<L->length; j++) /* 共有n-1趟排序 */ { flag=TRUE ; for (k=1; k<=L->length-j; k++) /* 一趟排序 */ if (LT(L->R[k+1].key, L->R[k].key ) ) { flag=FALSE ; L->R[0]=L->R[k] ; L->R[k]=L->R[k+1] ; L->R[k+1]=L->R[0] ; } if (flag==TRUE) break ; } } 故时间复杂度：T(n)=O(n²) 空间复杂度：S(n)=O(1) 算法分析 时间复杂度 ◆ 最好情况(正序)：比较次数：n-1；移动次数：0； ◆ 最坏情况(逆序)： 比较次数： ∑(n-i)= n-1 i=1 n(n-1) 2 移动次数： 3∑(n-i)= n-1 i=1 3n(n-1) 2 18 §10.3.2 快速排序 划分交换排序，1962年由Hoare(1980图灵奖)提出。 „ 分治法：将原问题分解为若干个规模较小但结构与原问题相 似的子问题；递归地求解这些子问题，然后将这些子问题的 解组合为原问题的解。 因此在用递归描述的分治算法的每一层递归上，都有如下三 个步骤： ① 分解（divide）：将原问题分解为若干个子问题，此步称 为划分； ② 求解（conquer）：递归地解各子问题，若子问题的size 足够小，则直接求解； ③ 组合（combine）：将各子问题的解组合为原问题的解。 第2步最易，表示为递归调用语句，分解和组合的难易取 决于应用