数据结构 第10章 排序2-快速排序.ppt

《数据结构 第10章 排序2-快速排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第10章排序数据结构讲义-快速排序10.3交换排序两两比较待排序记录的关键码，如果发生逆序（即排列顺序与排序后的次序正好相反），则交换之，直到所有记录都排好序为止。交换排序的主要算法有：1)冒泡排序2)快速排序交换排序的基本思想是：1)冒泡排序基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。前提：顺序存储结构例：关键字序列T=(21，25，49，25*，16，08），请写出冒泡排序的具体实现过程。21，25，49

2、，25*，16，0821，25，25*，16，08，4921，25，16，08，25*，4921，16，08，25，25*，4916，08，21，25，25*，4908，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）voidbubble_sort(SqList*L){intm,i,j,flag=1;RecordTypex;m=n-1;while((m>0)&&(

3、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（n2)—因为要考虑最坏情况空间效率：O（1）—只在交换时用到一个缓冲单元稳定性：稳定—25和25*在排序前后的次序未改变详细分析：最好情况：初始排列已经有序，只执行一趟起泡，做n-1次关键码比较，不移动对象。最坏情形：初始排列逆序，算法要执行n-1趟起泡，第i趟(1in)做了n-i次关键码比较

4、，执行了n-i次对象交换。此时的比较总次数KCN和记录移动次数RMN为：2）快速排序从待排序列中任取一个元素(例如取第一个)作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。基本思想：优点：因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快！前提：顺序存储结构()，设以首元素为枢轴中心例1：关键字序列T=(21，25，49，25*，16，08），请写出快速排序的算法步骤。21，25，49，25*，16，08初态：第1趟：第2趟

5、：第3趟：问题：1.这种不断划分子表的过程，计算机如何自动实现？2.“快速排序”是否真的比任何排序算法都快？08，16，21，25，25*，(49)2116，08，()25，25*，49(08)，16，21，25，(25*，49)1.这种不断划分子表的过程，计算机如何自动实现？编程时：①每一趟的子表的形成是采用从两头向中间交替式逼近法；②由于每趟中对各子表的操作都相似，主程序可采用递归算法。具体程序可见教材P275Low=high=3，本趟停止，将支点定位并返回位置信息例2：关键字序列T=(21，25，49，25*，16，08），请写出快速排序算法的一趟实现过

6、程。r[i]0123456初态21254925*1608第1趟highlow210825164925*321pivotkey=2108251649(08，16）21（25*，49，25）25*跑到了前面，不稳定！快速排序练习设要将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码按字母序的升序重新排列。快速排序一趟扫描的结果是。（F,H,C,D,P,A,M,Q,R,S,Y,X）快速排序算法详细分析：快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数（新的low和high）。可以证明，函数quicksort的平均计算时间也是O(nlog2

7、n)。实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。最大递归调用层次数与递归树的深度一致，理想情况为log2(n+1)。因此，要求存储开销为o(log2n)。如果每次划分对一个对象定位后，该对象的左侧子序列与右侧子序列的长度相同，则下一步将是对两个长度减半的子序列进行排序，这是最理想的情况。此时，快速排序的趟数最少。在最坏的情况，即待排序对象序列已经按其关键码从小到大排好序的情况下，其递归树成为单支树，每次划分只得到一个比上一次少一个对象的子序列。这样，必须经过n-1趟才能把所有对象定位，而且第i趟需要经过n-i次关键

8、码比较才能找到第i个对象的安放位置，总