数据结构第八章排序-修改.ppt

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

1、排序的基本概念插入排序交换排序选择排序归并排序基数排序各种方法的比较第八章排序1什么是排序(Sorting)？简单地说，排序就是将一组杂乱无章的数据按一定的规律排列起来（递增或递减）。排序是计算机中经常遇到的操作。§8.1排序的概念2数据表(DataList)待排序的记录的有限集合。关键字(Key)作为排序依据的各记录中的属性域。数据表：{R1，R2，R3，……，Rn}关键字序列：{k1，k2，k3，……，kn}排序(Sorting)使一组任意排列的数据表变成一组按关键字线性有序（递增或递减）的数据表。数据表：{R’1，R’2，R’3，……

2、，R’n}关键字序列：{k’1，k’2，k’3，……，k’n}其中：递增次序：k’1≤k’2≤k’3≤……≤k’n或递减次序：k’1≥k’2≥k’3≥……≥k’n排序前：排序后：排序的概念3例：5，2，8，5*排序后为：2，5，5*，8是稳定排序排序后为：2，5*，5，8是不稳定排序排序的分类排序算法的稳定性关键字相同的记录在排序过程中保持前后次序不变的排序称稳定排序，否则称不稳定排序。内排序与外排序*内排序是指在排序过程中记录全部存放在内存的排序；*外排序是指在排序过程中数据量太大，不能同时存放在内存，在排序过程中不断进行内、外存之间数据

3、交换的排序。4数据表的存储方式*顺序存储方式通过移动记录的相对存储位置实现排序。排序的分类*链式存储方式通过各结点修改指针实现排序301144772288112230447788排序前排序后h3011447722h3011447722排序前排序后5排序的时间效率:通常用算法执行中的数据比较次数与数据移动次数来衡量。排序的空间效率：在算法执行时所需的附加存储空间多少来衡量。排序算法分析为简单起见，数据的存储结构采用顺序方式存储，同时假定关键字是整数。记录存储数据类型如下：typedefstruct{intkey;/*存放关键字*/data

4、typeother;/*存放其他数据项*/}rectype;/*记录数据类型*/rectypeR[n+1];/*R[1]…R[n]存放n个记录*/按关键字递增次序排序6§8.2插入排序(InsertSorting)基本原理:将一个待排序的记录,按其关键字大小,插入到前面已经排好序的一组记录的适当位置上,直到记录全部插入为止。排序方法直接插入排序(InsertSort)希尔排序(ShellSort)7基本思想:将第i个记录插入在前i-1个有序的记录中，使前i个记录有序。直接插入排序(InsertSort)k1，k2，……ki-1，ki有序k1

5、，k2，…ki…ki-1有序例：10，20，30，40，50，2510，20，25，30，40，508主要操作3033442211123450123453322114430441112345temp442211333030443333304433333030222211主要操作步骤：*temp暂存R[i],*将比其大的所有记录依次后移*temp(R[i])插入。监视哨作用：*暂存R[i]*检测越界R[0]R[0]11304494938659776132749’012345678初始4938659776132749’第一趟第二趟3849659

6、776132749’4938384938656565第三趟3849659776132749’第四趟3849659776132749’第五趟3849657697132749’第六趟1338496576972749’第七趟1327384965769749’97979776769776131397766549381349’272797766549382749’97766549’主要步骤：*R[0]暂存R[i]*将比其大的所有记录依次后移*R[0]写入第i-1趟：（1）R[0]=R[i]（2）j初值？（3）若R[j].key>R[0].keyR[j

7、]后移（4）j下一个（前移）（5）重复（3）（4）直到？（6）R[?]=R[0]i的初值？终值？i-1j+12n10第i趟：（1）R[0]=R[i]（2）j初值？（3）若R[j].key>R[0].keyR[j]后移（4）j下一个（前移）（5）重复（3）（4）直到？（6）R[?]=R[0]i的初值？终值？insertsort(rectypeR[],n){for(i=2;i<=n;i++){R[0]=R[i];/*暂存第i个记录*/j=i-1;while(R[j].key>R[0].key)/*将所有大的记录后移*/{R[j+1]=R[j];

8、j--;}R[j+1]=R[0];/*插入*/}}直接插入排序的算法i-1j+12n11直接插入排序算法分析时间性能：直接插入排序算法由两重循环组成，外循环为n-1趟排序；内循环