欢迎来到天天文库
浏览记录
ID:53051273
大小:4.62 MB
页数:63页
时间:2020-04-16
《数据结构.第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、Kj(1≤i≤n,1≤j≤n,
2、i≠j)分别为记录Ri、Rj的关键字,且Ki=Kj,在排序前的序列中Ri领先于Rj(即i3、内部排序;反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。插入排序§10.2插入排序直接插入排序初始状态4938659776132749R0R1R2R3R4R5R6R7R8i=2i=33849659776132749i=43849659776132749i=5384965769713274976i=6384965769713274913i=7384965769713274927i=838496576971327494949386597761327493849387趟排序1趟排序2趟排序排序过程4、:先将序列中第1个记录看成是一个有序子序列,然后从第2个记录开始,逐个进行插入,直至整个序列有序。直接插入排序§10.2插入排序voidInsertSort(SqList&L){//对顺序表L作直接插入排序。for(i=2;i<=L.length;++i)if(L.r[i].key5、=L.r[i-1];for(j=i-2;L.r[0].key6、序过程中,不会通过比较而相互交换。折半插入排序§10.2插入排序(1)基本思想考虑到L.r[1,..,i-1]是按关键字有序的有序序列,则可以利用折半查找实现“L.r[1,…,i-1]中查找L.r[i]的插入位置”如此实现的插入排序为折半插入排序。例:有6个记录,前5个已排序的基础上,对第6个记录排序。[1527365369]42[1527365369]42[1527365369]42[152736425369]§10.2插入排序(high36)(42<53)highmidlo7、wlowhighmidhighlow折半插入排序在寻找插入位置时,不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多,改进效果越明显。折半插入排序算法§10.2插入排序voidBinsertSort(SqList&L){//折半插入排序inti,low,high,mid;for(i=2;i<=L.length;++i){L.r[0]=L.r[i];//将L.r[i]暂存到L.r[0]low=1;high=i-1;While(low<=high){//比较,折半查找插入位置mid=(low+high)/2;//折半if(L8、.r[0].key=lo
3、内部排序;反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。插入排序§10.2插入排序直接插入排序初始状态4938659776132749R0R1R2R3R4R5R6R7R8i=2i=33849659776132749i=43849659776132749i=5384965769713274976i=6384965769713274913i=7384965769713274927i=838496576971327494949386597761327493849387趟排序1趟排序2趟排序排序过程
4、:先将序列中第1个记录看成是一个有序子序列,然后从第2个记录开始,逐个进行插入,直至整个序列有序。直接插入排序§10.2插入排序voidInsertSort(SqList&L){//对顺序表L作直接插入排序。for(i=2;i<=L.length;++i)if(L.r[i].key5、=L.r[i-1];for(j=i-2;L.r[0].key6、序过程中,不会通过比较而相互交换。折半插入排序§10.2插入排序(1)基本思想考虑到L.r[1,..,i-1]是按关键字有序的有序序列,则可以利用折半查找实现“L.r[1,…,i-1]中查找L.r[i]的插入位置”如此实现的插入排序为折半插入排序。例:有6个记录,前5个已排序的基础上,对第6个记录排序。[1527365369]42[1527365369]42[1527365369]42[152736425369]§10.2插入排序(high36)(42<53)highmidlo7、wlowhighmidhighlow折半插入排序在寻找插入位置时,不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多,改进效果越明显。折半插入排序算法§10.2插入排序voidBinsertSort(SqList&L){//折半插入排序inti,low,high,mid;for(i=2;i<=L.length;++i){L.r[0]=L.r[i];//将L.r[i]暂存到L.r[0]low=1;high=i-1;While(low<=high){//比较,折半查找插入位置mid=(low+high)/2;//折半if(L8、.r[0].key=lo
5、=L.r[i-1];for(j=i-2;L.r[0].key6、序过程中,不会通过比较而相互交换。折半插入排序§10.2插入排序(1)基本思想考虑到L.r[1,..,i-1]是按关键字有序的有序序列,则可以利用折半查找实现“L.r[1,…,i-1]中查找L.r[i]的插入位置”如此实现的插入排序为折半插入排序。例:有6个记录,前5个已排序的基础上,对第6个记录排序。[1527365369]42[1527365369]42[1527365369]42[152736425369]§10.2插入排序(high36)(42<53)highmidlo7、wlowhighmidhighlow折半插入排序在寻找插入位置时,不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多,改进效果越明显。折半插入排序算法§10.2插入排序voidBinsertSort(SqList&L){//折半插入排序inti,low,high,mid;for(i=2;i<=L.length;++i){L.r[0]=L.r[i];//将L.r[i]暂存到L.r[0]low=1;high=i-1;While(low<=high){//比较,折半查找插入位置mid=(low+high)/2;//折半if(L8、.r[0].key=lo
6、序过程中,不会通过比较而相互交换。折半插入排序§10.2插入排序(1)基本思想考虑到L.r[1,..,i-1]是按关键字有序的有序序列,则可以利用折半查找实现“L.r[1,…,i-1]中查找L.r[i]的插入位置”如此实现的插入排序为折半插入排序。例:有6个记录,前5个已排序的基础上,对第6个记录排序。[1527365369]42[1527365369]42[1527365369]42[152736425369]§10.2插入排序(high36)(42<53)highmidlo
7、wlowhighmidhighlow折半插入排序在寻找插入位置时,不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多,改进效果越明显。折半插入排序算法§10.2插入排序voidBinsertSort(SqList&L){//折半插入排序inti,low,high,mid;for(i=2;i<=L.length;++i){L.r[0]=L.r[i];//将L.r[i]暂存到L.r[0]low=1;high=i-1;While(low<=high){//比较,折半查找插入位置mid=(low+high)/2;//折半if(L
8、.r[0].key=lo
此文档下载收益归作者所有