数据结构之排序算法讲义ppt课件.ppt

《数据结构之排序算法讲义ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、在此幻灯片插入公司的徽标从“插入”菜单选择图片找到徽标文件单击“确定”重新设置徽标大小单击徽标内任意位置。徽标外部出现的方框是“调整控点”使用这些重新设置对象大小如果在使用尺寸调整控点前按下shift键，则对象改变大小但维持原比例。DATA1065865姓名学号成绩班级李红976105995机97.6ABCDEFG数据结构注意带以下内容：图2-8-1图2-8-2图2-8-3图2-8-4图2-8-52021/7/302第二章 数据结构与算法(续)2021/7/3032.8排序2.8.1概述1、排序的功能：将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列。2、排序过程的组成步骤：

2、首先比较两个关键字的大小；然后将记录从一个位置移动到另一个位置。2021/7/304假设待排序的记录存放在地址连续的一组存储单元中，那么这种存储方式下的数据类型可描述为：MAX01234………keyinfo#defineMAX20typedefstruct{intkey;floatotherinfo;}RedType;2021/7/305排序方法插入排序选择排序交换排序归并排序直接插入排序折半插入排序简单选择排序堆排序起泡排序快速排序2021/7/3062.8.2插入排序直接插入、折半插入1、直接插入排序:基本思想：从数组的第2号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的

3、数组的适当位置上。举例：图8-2-12021/7/3072.8.2插入排序直接插入、折半插入该算法适合于n较小的情况，时间复杂度为O(n2).1、直接插入排序:基本思想：从数组的第2号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上待排元素序列：[53]2736156942第一次排序：[2753]36156942第二次排序：[273653]156942第三次排序：[15273653]6942第四次排序：[1527365369]42第五次排序：[152736425369]直接插入排序示例对于有n个数据元素的待排序列，插入操作要进行n-1次2021/7/308voi

4、dinsertSort(RedTypeL[],intn){inti,j;for(i=2;i<=n;i++)if(L[i].key

5、入一个关键字。举例，图8-2-22021/7/30102、折半插入排序折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。例：有6个记录，前5个已排序的基础上，对第6个记录排序。[1527365369]42lowmidhigh[1527365369]42lowhighmid[1527365369]42highlow[152736425369](high36)(42<53)2021/7/3011voidBinsertSort(RedTypeL[],intn){in

6、ti,low,high,mid;for(i=2;i<=n;++i){L[0]=L[i];/*r[0]作为监视哨*/low=1;high=i-1;While(low<=high){mid=(low+high)/2;if(L[0].key=high+1;j)L[j+1]=L[j];/*记录后移*/L[high+1]=L[0];/*插入*/}/*for*/}/*折半插入排序*/折半插入排序减少了关键字的比较次数，但记录的移动次数不变，其时间复杂度与直接插入排序相同。/*折半后的位

7、置*/2021/7/30121、简单选择排序思想：首先从1~n个元素中选出关键字最小的记录交换到第一个位置上。然后再从第2个到第n个元素中选出次小的记录交换到第二个位置上，依次类推。时间复杂度为O(n2)，适用于待排序元素较少的情况。2.8.3选择排序简单选择排序、堆排序举例：图8-2-32021/7/30132.8.3选择排序简单选择排序、堆排序。1、简单选择排序思想：首先从1~n个元素中选出关