素(或记录)的任意序列.ppt

《素(或记录)的任意序列.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第九章排序排序定义——将一个数据元素（或记录）的任意序列，重新排列成一个按关键码有序的序列叫~排序分类按待排序记录所在位置内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问的排序排序的稳定性若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的，否则为不稳定的排序基本操作比较两个关键字大小将记录从一个位置移动到另一个位置9.1基本概念排序方法：内排序插入排序：直接插入排序、折半插入排序、表插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、树形选择排序、堆排序归并排序：2-路归并排序基数排序：多关键码排序、链式基数排序外排

2、序：多路平衡归并按排序所需工作量简单的排序方法：T(n)=O(n²)先进的排序方法：T(n)=O(logn)基数排序：T(n)=O(d.n)9.2插入排序9.2.1直接插入排序排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序基本思想：每次将一个待排序的记录，按其关键码大小插入到前面已经排好序的子序列的适当位置，直到全部记录插入完成。例49386597761327i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=5

3、76(3849657697)1327i=613(133849657697)27i=1()i=7(133849657697)2727jjjjjj977665493827(13273849657697)排序结果：算法描述for(i=2;i<=n;i++){设置监视哨；寻找插入位置；移动元素；插入；}可以边寻找插入位置边移动元素。算法评价时间复杂度最好情况：若待排序记录按关键字从小到大排列(正序)关键字比较次数：记录移动次数：最坏情况：若待排序记录按关键字从大到小排列(逆序)关键字比较次数：记录移动次数：若待排序记录是随机的，取平均值关键字比较次数：记录移动次数：T(n)=O(n²

4、)空间复杂度：S(n)=O(1)9.2.2折半插入排序排序过程：用折半查找方法确定插入位置的排序叫~例i=1(30)1370853942620i=213(1330)70853942620i=76(6133039427085)20…...i=820(6133039427085)20lhmi=820(6133039427085)20lhmi=820(6133039427085)20ljmhi=820(6133039427085)20lhi=820(613203039427085)for(i=2;i<=n;i++){设置监视哨；寻找插入位置；移动元素；插入；}算法描述算法评价时间复

5、杂度：T(n)=O(n²)空间复杂度：S(n)=O(1)9.2.3表插入排序0123456784938659776132749keynextMAXINT00123456784938659776132749keynextMAXINT231400123456784938659776132749keynextMAXINT10i=1i=4i=50123456784938659776132749keynextMAXINT2314045for(i=1;i<=n;i++){寻找插入位置；修改指针；}9.2.4希尔排序(缩小增量法)排序过程：先取一个正整数d1

6、，组内进行直接插入排序；然后取d2

7、{inti,j;for(i=dk+1;i<=n;i++){r[0].key=r[i].key;j=i-dk;while(j>0&&r[0].key