快速排序9.4 选择排序9.5 归并排序9.6 基数排序9.7 内部排序.ppt

《快速排序9.4 选择排序9.5 归并排序9.6 基数排序9.7 内部排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、9.1概述9.2插入排序9.3快速排序9.4选择排序9.5归并排序9.6基数排序9.7内部排序方法的比较第9章内部排序1本章重点难点重点：插入排序、快速排序、选择排序、归并排序、基数排序的思想和算法。难点：堆排序的思想和算法，在实际应用中如何根据实际情况，选择最优的排序算法。29.1概述9.2插入排序9.3快速排序9.4选择排序9.5归并排序9.6基数排序9.7内部排序方法的比较第9章内部排序39.1概述排序方法的稳定和不稳定张三80分李四75分王五85分陈六90分李四75分张三80分王五85分陈六90分陈六90分王

2、五85分张三80分李四75分当需要排序的关键字都不相同时,排序的结果是唯一的;4当排序的关键字中存在相同的情况时,排序方法不唯一;张三80分李四75分王五85分陈六80分李四75分张三80分陈六80分王五85分李四75分陈六80分张三80分王五85分在排序前后，含相等关键字的记录的相对位置保持不变，称这种排序方法是稳定的；9.1概述反之，含相等关键字的记录的相对位置有可能改变，称这种排序方法是不稳定的。5内部排序和外部排序9.1概述排序期间文件的全部记录不能同时存放在计算机的内存中，要借助计算机的外存才能完成排序，称

3、之为“外部排序”。在排序过程中，只使用计算机的内存存放待排序记录，称这种排序为内部排序。内外存之间的数据交换次数就成为影响外部排序速度的主要因素。6#defineMAXSIZE1000//待排顺序表最大长度typedefintKeyType;//关键字类型为整数类型typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其它数据项}RcdType;//记录类型typedefstruct{RcdTyper[MAXSIZE+1];//r[0]闲置intlength;//顺序表

4、长度}SqList;//顺序表类型存储结构9.1概述7效率分析9.1概述(1)时间复杂度：关键字的比较次数和记录移动次数。(2)空间复杂度：执行算法所需的附加存储空间。(3)稳定算法和不稳定算法89.1概述9.2插入排序9.3快速排序9.4选择排序9.5归并排序9.6基数排序9.7内部排序方法的比较第9章内部排序99.2、插入排序9.2.1直接插入排序9.2.2其他插入排序9.2.3希尔排序10插入排序的思想9.2.1直接插入排序(1)一个记录是有序的；(2)从第二个记录开始，将每个记录插入到已排好序的序列中；(3)

5、一直进行到第n个记录。11算法概述9.2.1直接插入排序(1)将序列中的第1个记录看成是一个有序的子序列;(2)从第2个记录起逐个进行插入，直至整个序列变成按关键字有序序列为止；整个排序过程需要进行比较、后移记录、插入适当位置。从第二个记录到第n个记录共需n-1趟。1249386538.761327493849386538.7613274938496538.761327493838496538.761327496538496538.7613274938.38496538.7613274938.384965761327

6、4938.3838.4965761327499.2.1直接插入排序直接插入排序示例演示13voidInsertionSort(SqList&L){//对顺序表L作直接插入排序。for(i=2;i<=L.length;++i)if(L.r[i].key

7、2.1直接插入排序直接插入排序算法14算法分析9.2.1直接插入排序(1)稳定性直接插入排序是稳定的排序方法。(2)算法效率a.时间复杂度最好情况:比较O(n),移动O(1);最坏情况:比较O(n2),移动O(n2);平均O(n2)b.空间复杂度O(1)。15折半插入排序思想9.2.2其它插入排序(1)在直接插入排序中，r[1..i-1]是一个按关键字有序的有序序列;(2)可以利用折半查找实现“在r[1..i-1]中查找r[i]的插入位置”;(3)称这种排序为折半插入排序。16012345678910查2205131

8、92137566475808890lowhighmid=(low+high)/2high=mid-1midlow=mid+1midlow=mid+1high=mid-19.2.2其它插入排序折半插入排序的演示过程17voidBiInsertionSort(SqList&L){for(i=2;i<=L.length;++i){L.r[0]=L.r