《武汉理工大学 信息工程学院 数据结构ch 排序快速排序.pptx》由会员分享，可在线阅读，更多相关《武汉理工大学 信息工程学院 数据结构ch 排序快速排序.pptx（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、10.3 10.3 交换排序交换排序的基本思想是：交换排序的基本思想是：两两比较待排序记录的关键两两比较待排序记录的关键两两比较待排序记录的关键两两比较待排序记录的关键码，如果发生逆序（即排列顺序与排序后的次序正好码，如果发生逆序（即排列顺序与排序后的次序正好码，如果发生逆序（即排列顺序与排序后的次序正好码，如果发生逆序（即排列顺序与排序后的次序正好相反），则交换之，直到所有记录都排好序为止。相反），则交换之，直到所有记录都排好序为止。相反），则交换之，直到所有记录都排好序为止。相反），则交换之，直到所有记录都排好序为止。交换排序的主要算法有：交换排序的主要算法有：1)冒泡排序冒泡排序 2)快
2、速排序快速排序第1页/共14页 1)冒泡排序基本思路：基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。优点：优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。其他元素；一旦下趟没有交换发生，还可以提前结束排序。前提：顺序存储结构 例：关键字序列 T=(21，25，49，25*，16，08），请写出冒泡排序的具体实现过程。21，25，49，25*，16，0821，25，25*，16，08，4921，25，16，08，25*，4921，1
3、6，08，25，25*，4916，08，21，25，25*，4908，16，21，25，25*，49初态：初态：第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟第2页/共14页void bubble_sort(SqList*L)int m,i,j,flag=1;RecordType x;m=n-1;while(m0)&(flag=1)flag=0;for(j=1;jrj.keyL-rj+1.key)flag=1;x=L-rj;L-rj=L-rj+1;L-rj+1=x;m-;第3页/共14页冒泡排序的算法分析时间效率：时间效率：时间效率：时间效率：O O O O（n n n n2 2 2 2)
4、因为要考虑最坏情况因为要考虑最坏情况因为要考虑最坏情况因为要考虑最坏情况空间效率：空间效率：空间效率：空间效率：O O O O（1 1 1 1）只在交换时用到一个缓冲单元只在交换时用到一个缓冲单元只在交换时用到一个缓冲单元只在交换时用到一个缓冲单元稳稳稳稳 定定定定 性：性：性：性：稳定稳定稳定稳定 25252525和和和和25252525*在排序前后的次序未改变在排序前后的次序未改变在排序前后的次序未改变在排序前后的次序未改变详细分析：详细分析：最好情况：最好情况：初始排列已经有序，只执行一趟起泡，做初始排列已经有序，只执行一趟起泡，做 n-1 次关键码比较，不次关键码比较，不移动对象。移动
5、对象。最坏情形：最坏情形：初始排列逆序，初始排列逆序，算法要执行算法要执行n-1 1趟起泡，第趟起泡，第i趟趟(1 i n)做了做了n-i 次关键码比较，执行了次关键码比较，执行了n-i 次对象交换。此时的比较总次数次对象交换。此时的比较总次数KCN和记录移动次和记录移动次数数RMN为：为：第4页/共14页2）快速排序 从待排序列中任取一个元素从待排序列中任取一个元素从待排序列中任取一个元素从待排序列中任取一个元素 (例如取第一例如取第一例如取第一例如取第一个个个个)作为作为作为作为中心中心中心中心，所有比它小的元素一律前放，所，所有比它小的元素一律前放，所，所有比它小的元素一律前放，所，所有
6、比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；有比它大的元素一律后放，形成左右两个子表；有比它大的元素一律后放，形成左右两个子表；有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调然后再对各子表重新选择中心元素并依此规则调然后再对各子表重新选择中心元素并依此规则调然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有整，直到每个子表的元素只剩一个。此时便为有整，直到每个子表的元素只剩一个。此时便为有整，直到每个子表的元素只剩一个。此时便为有序序列了。序序列了。序序列了。序序列了。基本思想：基本思想：基本思想：基
7、本思想：优点：优点：优点：优点：因为每趟可以确定不止一个元素的位置，而且因为每趟可以确定不止一个元素的位置，而且因为每趟可以确定不止一个元素的位置，而且因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快！呈指数增加，所以特别快！呈指数增加，所以特别快！呈指数增加，所以特别快！前提：前提：前提：前提：顺序存储结构顺序存储结构 第5页/共14页设以首元素为枢轴中心设以首元素为枢轴中心()，例1：关键字序列 T=(21，25，49，25*，16，08），请写出快速排序的算法步骤。21，25，49，25*，16，08初态：初态：第第1趟：趟：第第2趟：趟：第第3趟：趟：问题：问题：问题：问
8、题：1.1.1.1.这种不断划分子表的过程，计算机如何自动实现？这种不断划分子表的过程，计算机如何自动实现？这种不断划分子表的过程，计算机如何自动实现？这种不断划分子表的过程，计算机如何自动实现？2.2.2.2.“快速排序快速排序快速排序快速排序”是否真的比任何排序算法都快？是否真的比任何排序算法都快？是否真的比任何排序算法都快？是否真的比任何排序算法都快？08，16，21，25，25*，(49)2116，08，()25，25*，49(08)，16，21，25，(25*，49)第6页/共14页1.1.这种不断划分子表的过程，计算机如何自这种不断划分子表的过程，计算机如何自动实现？动实现？编程时
9、：编程时：每一趟的子表的形成是采用从两头向中间交每一趟的子表的形成是采用从两头向中间交替式逼近法；替式逼近法；由于每趟中对各子表的操作都相似，主程序由于每趟中对各子表的操作都相似，主程序可采用递归算法。可采用递归算法。具体程序可见教材具体程序可见教材P275P275第7页/共14页Low=high=Low=high=Low=high=Low=high=3 3 3 3，本趟停止，将支点定位本趟停止，将支点定位本趟停止，将支点定位本趟停止，将支点定位并返回位置信息并返回位置信息并返回位置信息并返回位置信息例2：关键字序列 T=(21，25，49，25*，16，08），请写出快速排序算法的一趟实现过
10、程。ri0123456初态初态21254925*1608第第1趟趟highhighlowlow210825164925*321pivotkey=pivotkey=212108251649(08，16）21 （25*，49，25 ）25252525*跑到了前面，跑到了前面，跑到了前面，跑到了前面，不稳定不稳定不稳定不稳定！第8页/共14页快速排序练习设要将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码按字母序的升序重新排列。快速排序一趟扫描的结果是 。l（F,H,C,D,P,A,M,Q,R,S,Y,X）第9页/共14页快速排序算法详细分析：快速排序算法详细分析：n快速排序是递归
11、的，需要有一个栈存放每层递归调用快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数时的指针和参数（新的（新的lowlow和和highhigh）。n可以证明，函数可以证明，函数quicksort的平均计算时间也是的平均计算时间也是O(nlog2n)。实验结果表明：就平均计算时间而言，快实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个速排序是我们所讨论的所有内排序方法中最好的一个。n最大递归调用层次数与递归树的深度一致，理想情况最大递归调用层次数与递归树的深度一致，理想情况为为 log2(n+1)。因此，要求存储开销为。因此，要求存储开销为 o(log2
12、n)。n如果每次划分对一个对象定位后，该对象的左侧子序如果每次划分对一个对象定位后，该对象的左侧子序列与右侧子序列的长度相同，则下一步将是对两个长度列与右侧子序列的长度相同，则下一步将是对两个长度减半的子序列进行排序，这是最理想的情况。此时，快减半的子序列进行排序，这是最理想的情况。此时，快速排序的趟数最少。速排序的趟数最少。第10页/共14页n在最坏的情况，即待排序对象序列已经按在最坏的情况，即待排序对象序列已经按其关键码从小到大排好序的情况下，其关键码从小到大排好序的情况下，其递归其递归树成为单支树树成为单支树，每次划分只得到一个比上一，每次划分只得到一个比上一次少一个对象的子序列。这样，
13、必须经过次少一个对象的子序列。这样，必须经过 n-1 趟才能把所有对象定位，而且第趟才能把所有对象定位，而且第 i 趟需趟需要经过要经过 n-i 次关键码比较才能找到第次关键码比较才能找到第 i 个对个对象的安放位置，总的关键码比较次数将达到象的安放位置，总的关键码比较次数将达到n n2 2/2/2n 快速排序是一个快速排序是一个不稳定不稳定的排序方法的排序方法第11页/共14页问题问题2.2.“快速排序快速排序”是否真的比任何排序算法都快是否真的比任何排序算法都快？设每个子表的支点都在中间（比较均衡），则：设每个子表的支点都在中间（比较均衡），则：第第1 1趟比较，可以确定趟比较，可以确定1
14、 1个元素的位置；个元素的位置；第第2 2趟比较（趟比较（2 2个子表），可以再确定个子表），可以再确定2 2个元素的位置；个元素的位置；第第3 3趟比较（趟比较（4 4个子表），可以再确定个子表），可以再确定4 4个元素的位置；个元素的位置；第第4 4趟比较（趟比较（8 8个子表），可以再确定个子表），可以再确定8 8个元素的位置；个元素的位置；只需只需 loglog2 2n n 1 1趟便可排好序。趟便可排好序。基本上是！因为每趟可以确定的数据元素是呈指数增加的！基本上是！因为每趟可以确定的数据元素是呈指数增加的！而且，每趟需要比较和移动的元素也呈指数下降，加上编程时使用了交替逼近技而且，
15、每趟需要比较和移动的元素也呈指数下降，加上编程时使用了交替逼近技巧，更进一步减少了移动次数，所以速度特别快。巧，更进一步减少了移动次数，所以速度特别快。教材教材P276P276有证明：快速排序的平均排序效率为有证明：快速排序的平均排序效率为O(nlogO(nlog2 2n)n)；但最坏情况但最坏情况(例如已经有序例如已经有序)下仍为下仍为O(nO(n2 2),),改进措施见改进措施见P277P277。第12页/共14页作业 以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，分别写出执行以下算法的各趟排序结束时，关键字序列的状态。冒泡排序 快速排序第13页/共14页感谢您的观看！第14页/共14页