数据结构讲义第10章-排序讲课讲稿.ppt

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

1、数据结构讲义第10章-排序10.1概述学号姓名性别出生日期来源总分录取专业年月日┆200109832001098420010985┆┆赵剑平蒋伟峰郭娜┆┆男男女┆┆198219821983┆┆110901┆┆051225┆┆石家庄一中保定三中易县中学┆┆593601598┆┆计算机计算机计算机┆1.排序的定义排序(sorting)是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按关键码有序的序列。10.1概述1.排序的定义（1）排序的定义：假设{R1,R2,…,Rn

2、}是由n个记录组成的文件，{K1,K2,…,Kn}是排序码集合，所谓排序是将记录按排序码递增（或递减）的排列。排序码可以是主关键码，也可以是次关键码。（2）稳定性假设Ki=Kj(1≤i,j≤n,ij)，且在排序前的序列中Ri领先于Rj(即i

3、(2)选择排序(3)交换排序(4)分配排序(5)归并排序(6)外部排序按排序所需的工作量，排序分为：(1)简单排序方法，其时间复杂度为O(n2)(2)先进的排序方法，其时间复杂度为O(nlogn)(3)基数排序，其时间复杂度为O(d·n)10.1概述1.排序的定义（4）排序中的基本操作：i)比较关键码大小ii)移动记录（5）对于待排序的记录序列，有三种常见的存储表示方法。①向量结构，即将待排序的记录存放在一组地址连续的存储单元中。②链表结构。③记录向量与地址向量结合，即将待排序记录存放在一组地址连

4、续的存储单元中，同时另设一个指示各个记录位置的地址向量。10.1概述1.排序的定义为简单起见，数据的存储结构采取向量的存储结构：#definen20//记录数typedefintkeytype;typedefstruct{keytypekey;datatypeother;}rectype;rectyper[n+1];10.1概述1.排序的定义（6）排序算法的评价：i)算法的执行时间ii)算法执行时所需的附加空间10.2插入排序基本原理：每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的

5、一组对象适当位置上，直到对象全部插入为止。10.2插入排序10.2.1直接插入排序1、直接插入排序的基本思想先假定第1个记录为有序序列，然后从第2条记录开始，依次将记录插入到前面已经有序的序列中，直至全部记录有序。一般情况下，第i趟直接插入排序：将r[i]插入到已经有序的序列r[1..i-1]中，使其变成有序序列r[1..i]。整个排序进行n-1趟插入。10.2插入排序10.2.1直接插入排序2、示例：初始：[49]38659776132749i=1:[3849]659776132749i=5:[

6、133849657697]2749i=3:[38496597]76132749i=2:[384965]9776132749i=4:[3849657697]132749i=6:[13273849657697]49i=7:[1327384949657697]10.2插入排序10.2.1直接插入排序3、算法：voidInsertSort(rectypeR[],intn){inti,j;for(i=2;i

7、[j+1]＝R[j];R[j+1]＝R[0]}}10.2插入排序10.2.1直接插入排序4、算法分析：空间效率：只需要一个记录的辅助空间。时间效率：比较记录的次数为：最小：n-1次；最大:(n+2)(n-1)/2次移动记录的次数：最小：2(n-1)最大:(n+4)(n-1)/2平均情况：O(n2)10.2插入排序10.2.2折半插入排序1、折半插入排序：将直接插入排序的查找过程改用折半查找。由此实现的排序称为二分法插入排序。10.2插入排序10.2.2折半插入排序2、示例：(1)132738496

8、5769749low=1mid=4high=7(2)1327384965769749low=5mid=6high=7(3)1327384965769749low=5mid=5high=5∵49’<65∴high=mid-1=4low=5>high∴已找到插入位置low=5(4)132738494965769710.2插入排序10.2.2折半插入排序3、算法：voidBinInsertSort(rectyper[],intn){for(i=2;i<=n;++i){x=r[i];low