文档介绍：第第 10 10 章章排序排序数据结构讲义 - 快速排序 交换排序交换排序两两比较待排序记录的关键两两比较待排序记录的关键码,如果发生逆序(即排列顺序与排序后的次序正好码,如果发生逆序(即排列顺序与排序后的次序正好相反),则交换之,直到所有记录都排好序为止。相反),则交换之,直到所有记录都排好序为止。交换排序的主要算法有: 1) 冒泡排序 2) 快速排序交换排序的基本思想是: 交换排序的基本思想是: 1) 1) 冒泡排序冒泡排序基本思路: 每趟不断将记录两两比较,并按“前小后大”(或“前大后小”)规则交换。优点: 每趟结束时,不仅能挤出一个最大值到最后面位置, 还能同时部分理顺其他元素;一旦下趟没有交换发生,还可以提前结束排序。前提: 顺序存储结构例: 关键字序列 T=(21 ,25,49,25*,16,08),请写出冒泡排序的具体实现过程。 21,25,49, 25 *,16, 08 21,25,25*,16, 08 ,49 21,25,16, 08 ,25*,49 21,16, 08 ,25,25*,49 16,08 ,21,25,25*,49 08,16,21,25,25*,49 初态: 第1趟第2趟第3趟第4趟第5趟冒泡排序练习冒泡排序练习?设要将序列( Q, H, C, Y, P, A, M, S, R, D, F, X )中的关键码按字母序的升序重新排列。冒泡排序一趟扫描的结果是。?( H, C, Q, P, A, M, S, R, D, F, X , Y ) void bubble_sort(SqList *L) { int m,i,j,flag=1; RecordType x; m=n-1; while((m>0)&&(flag==1)) { flag=0; for(j=1;j<=m;j++) if(L->r[j].key>L->r[j+1].key) { flag=1; x=L->r[j]; L->r[j]=L->r[j+1]; L->r[j+1]=x; } m--; }} 冒泡排序的算法分析冒泡排序的算法分析时间效率: 时间效率: O O( (n n 2 2) ) ——因为要考虑最坏情况因为要考虑最坏情况空间效率: 空间效率: O O( (1 1) )——只在交换时用到一个缓冲单元只在交换时用到一个缓冲单元稳稳定定性: 性: 稳定稳定——25 25和和25 25 * *在排序前后的次序未改变在排序前后的次序未改变详细分析: ?最好情况: 初始排列已经有序,只执行一趟起泡,做 n-1 次关键码比较,不移动对象。?最坏情形: 初始排列逆序, 算法要执行 n-1趟起泡,第 i趟(1?i?n)做了 n- i 次关键码比较,执行了 n-i 次对象交换。此时的比较总次数 KCN 和记录移动次数 RMN 为: ?????????????? 11 1112 33 12 1 ni ninnin RMN nnin KCN )()( )()( 2 2) )快速排序快速排序从待排序列中任取一个元素从待排序列中任取一个元素 ( (例如取第一例如取第一个个) ) 作为中心,所有比它小的元素一律前放,所作为中心,所有比它小的元素一律前放,所有比它大的元素一律后放,形成左右两个子表; 有比它大的元素一律后放,形成左右两个子表; 然后再对各子表重新选择中心元素并依此规则调然后再对各子表重新选择中心元素并依此规则调整,直到每个子表的元素只剩一个。此时便为有整,直到每个子表的元素只剩一个。此时便为有序序列了。序序列了。基本思想: 基本思想: 优点: 优点: 因为每趟可以确定不止一个元素的位置,而且因为每趟可以确定不止一个元素的位置,而且呈指数增加,所以特别快! 呈指数增加,所以特别快! 前提: 前提: 顺序存储结构顺序存储结构( ) , 设以首元素为枢轴中心例例1 1: :关键字序列关键字序列 T=(21 T=(21 , , 25 25 , , 49 49 , , 25 25 * *, , 16 16 , , 08 08 ), ), 请写出快速排序的算法步骤。请写出快速排序的算法步骤。 21, 25 , 49 , 25 *,16, 08 初态: 第1趟: 第2趟: 第3趟: 问题: 问题: 1. 1. 这种不断划分子表的过程,计算机如何自动实现? 这种不断划分子表的过程,计算机如何自动实现? 2. 2. ““快速排序快速排序””是否真的比任何排序算法都快? 是否真的比任何排序算法都快? 08,16,21,25,2