数据结构数10-排序ppt课件.ppt

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

1、华中科技大学计算机学院数据结构第十章内排序10.1概述1.排序----将文件或表中的记录，通过某种方法整理成按关键字大小次序排列的处理过程。假定n个记录的文件为(R1,R2,...,Rn)对应的关键字为(K1,K2,...,Kn)则排序是确定如下一个排列p1,p2,...,pn使得:Kp1≤Kp2≤...≤Kpn从而得到一个有序文件(Rp1,Rp2,...Rpn)学生成绩表20051刘大海807520042王伟908320066吴晓英828820038刘伟807020052王洋607012345学号姓名数学外语20038刘伟

2、807020042王伟908320051刘大海807520052王洋607020066吴晓英8288学号姓名数学外语20052王洋607020051刘大海807520038刘伟807020066吴晓英828820042王伟908320042王伟908317320066吴晓英828817020051刘大海807515520038刘伟807015020052王洋607013012345学号姓名数学外语学号姓名数学外语总分1234512345(a)无序表(b)按学号排列的有序表(c)按数学成绩排列的有序表(d)按总分成绩排列的有序

3、表2.什么是排序的稳定性假设在待排序的文件中，存在两个具有相同关键字的记录R(i)与R(j),其中R(i)位于R(j)之前。在用某种排序法排序之后,R(i)仍位于R(j)之前，则称这种排序方法是稳定的；否则，称这种排序方法是不稳定的。例数列(10,25,22,42,25,30,18)(10,18,22,25,25,30,42)(10,25,22,42,25,30,18)(10,18,22,25,25,30,42)稳定的排序不稳定的排序20051刘大海807520042王伟908320066吴晓英828820038刘伟8070

4、20052王洋607012345学号姓名数学外语20052王洋607020038刘伟807020051刘大海807520066吴晓英828820042王伟9083学号姓名数学外语12345(e)按数学成绩排列的有序表不稳定的排序3.内部排序(内排序)----在计算机内存中进行的排序外部排序(外排序)----借助计算机外存进行的排序4.待排序的记录和顺序表(文件)的数据类型#defineMAXSIZE20//最大长度typedefintKeyType；//关键字类型typedefstruct//记录类型{KeyTypekey；

5、//关键字InfoTypeotherinfo；//其它数据类型}RecType；//记录类型名typedefstruct{RecTyper[MAXSIZE+1]；//r[0]用作监视哨intlength;//实际表长}SeqList；//记录表类型或表和表长分别定义和说明RecTyper[MAXSIZE+1]；//r[0]用作监视哨intlength；//实际表长length≤MAXSIZE5.排序算法分析(1)时间复杂度对n个记录排序，所需比较关键字的次数；最好情况；最坏情况；平均情况对n个记录排序，所需移动记录的次数；最

6、好情况；最坏情况；平均情况(2)空间复杂度排序过程中，除文件中的记录所占的空间外，所需的辅助存储空间的大小。6.内排序方法(1)对顺序表的排序插入排序：直接插入排序；折半插入排序；2-路插入排序；表插入排序；希尔(Shell)排序；选择排序：简单选择/选择排序；树形选择排序；堆排序归并排序2-路归并排序k-路归并排序●交换排序冒泡排序：单向冒泡排序，双向冒泡排序快速排序●基数排序多关键字排序最高位优先法最低位优先法链式基数排序(2)对单链表的排序直接插入,简单选择,冒泡排序,基数排序10.2插入排序算法基本思想：将待排序的记

7、录插入到已排序的子文件中去，使得插入之后得到的子文件仍然是有序子文件；插入一个记录，首先要对有序子文件进行查找，以确定这个记录的插入位置；按查找方式的不同，插入排序又可以分为线性插入排序和折半插入排序，前者使用顺序查找，后者使用折半查找。1.直接插入排序(线性插入排序)设待排序的文件为：(r[1],r[2],...,r[n])关键字为：(r[1].key,r[2].key,...,r[n].key)首先,将初始文件中的记录r[1]看作有序子文件；第1遍：将r[2]插入有序子文件中，若：r[2].key

8、[2]插在r[1]之前；否则，插在r[1]的后面。第2遍：将记录r[3]插入前面已有2个记录的有序子文件中，得到3个记录的有序子文件。以此类推，依次插入r[4],...,r[n],最后得到n个记录的递增有序文件。例.直接插入排序,设K0为"监视哨”K0K1K2K3K4K5K6初始关键字：(