数据结构.第10章.排序.1.插入排序和交换排序ppt课件.ppt

《数据结构.第10章.排序.1.插入排序和交换排序ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构DataStructures张凯计算机学院软件工程系2011年3月12日第10章内部排序选择排序(直接排序、堆排序)概述插入排序(直接排序、折半排序、希尔排序)交换排序(冒泡排序、快速排序)归并排序基数排序概述§10.1概述排序：将数据元素的一个任意序列，重新排列成一个按关键字有序的序列。例：将关键字序列：52,49,80,36,14,58,61,23调整为：14,23,36,49,52,58,61,80若按主关键字排序则结果惟一若按次关键字排序则结果可以不惟一(因有相同关键字)概述§10.1概述设Ki、K

2、j(1≤i≤n,1≤j≤n,i≠j)分别为记录Ri、Rj的关键字，且Ki=Kj，在排序前的序列中Ri领先于Rj(即i

3、若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。插入排序§10.2插入排序直接插入排序初始状态4938659776132749R0R1R2R3R4R5R6R7R8i=2i=33849659776132749i=43849659776132749i=5384965769713274976i=6384965769713274913i=7384965769713274927i=838496576971327

4、494949386597761327493849387趟排序1趟排序2趟排序排序过程：先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。直接插入排序§10.2插入排序voidInsertSort(SqList&L){//对顺序表L作直接插入排序。for(i=2;i<=L.length;++i)if(L.r[i].key

5、ey的记录，在查找的同时实现记录向后移动；插入r[i];L.r[0]=L.r[i];//复制为监视哨L.r[i]=L.r[i-1];for(j=i-2;L.r[0].key

6、待排记录序列是随机的，取上述二值的平均值。所以直接插入排序的时间复杂度为O(n2)。直接插入排序是“稳定的”：关键码相同的两个记录，在整个排序过程中，不会通过比较而相互交换。折半插入排序§10.2插入排序(1)基本思想考虑到L.r[1,..,i-1]是按关键字有序的有序序列，则可以利用折半查找实现“L.r[1,…,i-1]中查找L.r[i]的插入位置”如此实现的插入排序为折半插入排序。例：有6个记录，前5个已排序的基础上，对第6个记录排序。[1527365369]42[1527365369]42[152736536

7、9]42[152736425369]§10.2插入排序(high36)(42<53)highmidlowlowhighmidhighlow折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。折半插入排序算法§10.2插入排序voidBinsertSort(SqList&L){//折半插入排序inti,low,high,mid;for(i=2;i<=L.length;++i){L.r[

8、0]=L.r[i];//将L.r[i]暂存到L.r[0]low=1;high=i-1;While(low<=high){//比较，折半查找插入位置mid=(low+high)/2;//折半if(L.r[0].key=lo