数据结构精品课件-交换类排序法.pptVIP

* * * * * * 9.1 排序的基本概念 9.2 插入类排序 9.3 交换类排序法 9.4 选择类排序法 9.5 归并排序 9.6 分配类排序 9.7 各种排序方法的综合比较 第九章 内部排序 9.8 总结与提高 9.3 交换类排序法 一、 起泡排序 二、 快速排序 三、 快速排序的时间分析 　　假设在排序过程中，记录序列r[1..n]的状态为： 一 趟起泡排序 无序序列r[1..i] 有序序列 r[i+1..n] i 无序序列r[1..i-1] 有序序列 r[i..n] 对无序序列，比较(交换)相邻记录，可将关键字最大的记录交换到 i 的位置上 有序序列大于无序序列 一、 起泡排序 算法一： void bubblesort(recordtype r[ ], int length); { n=length;change=true; for( i=n; i1change; --i) {change=false; change=true; } } for (j=1; ji ; ++j) if (r[j+1].key r[j].key) {x=r[j]; r[j]=r[j+1]; r[j+1]=x; } 稳定？ 算法二： void bubblesort(recordtype r[ ], int n); {i= n; while ( i 1) { laste=1; for (j=1; ji; j++) if (r[j+1].key r[j].key) {x=r[j]; r[j]=r[j+1]; r[j+1]=x; laste= j; } {记下进行交换的记录位置} i= laste; {本趟最后一次进行交换的记录位置} } } 5 2 3 1 9 7 8 注意: 2. 算法一每经过一趟“起泡”则“i减1”， 但算法二并不是每趟如此。 例如: 2 5 5 3 1 5 7 9 8 9 i=7 i=6 1 3 i=2 1. 起泡排序的结束条件为， 最后一趟没有进行“交换记录”。 laste laste 1 1 3 2 最好的情况（关键字在记录序列中顺序有序）： 只需进行一趟起泡 “比较”的次数： 最坏的情况（关键字在记录序列中逆序有序）： 需进行n-1趟起泡 “比较”的次数： 0 “移动”的次数： “移动”的次数： n-1 ?(i -1) = n i=2 n (n-1) 2 3?(i -1) = n i=2 3n (n-1) 2 所以，时间复杂度为O(n2) 时间分析: 起泡排序一趟之后，使最大的记录定位到最后,如果一趟之后可使某记录(任意)定位在它应处的位置(在有序序列中),而将其余的无序序列以它为枢轴,分成两部分,比它小的放在它的前面,比它大的的放在它的后面,下一趟分别对前后的子序列排序,显然可加快速度。 这就是快速排序 二、快速排序 　目标：找一个记录，以它的关键字作为“枢轴”，凡关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。 致使一趟排序之后，记录的无序序列r[s..t]将分割成两部分：r[s..i-1]和r[i+1..t]，且 r[j].key≤ r[i].key ≤ r[j].key (s≤j≤i-1) 枢轴 (i+1≤j≤t)。 一趟快速排序（一次划分） low high 设 r[s]=52 为枢轴 将 r[high].key 和枢轴的关键字进行比较， 要求 r[high].key ≥ 枢轴的关键字 将 r[low].key 和 枢轴的关键字进行比较， 要求 r[low].key ≤ 枢轴的关键字 high low high low 52 49 80 36 14 58 61 97 23 75 s t r[s] 52 high high high low low 23 80 14 52 例如 可见，经过“一次划分”，将关键字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 变为: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在调整过程中，设立了两个指针：