资源描述：
《数据结构-第十章-排序.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学号姓
2、名数学外语20038刘伟807020042王伟908320051刘大海807520052王洋607020066吴晓英8288学号姓名数学外语20052王洋607020051刘大海807520038刘伟807020066吴晓英828820042王伟908320042王伟908317320066吴晓英828817020051刘大海807515520038刘伟807015020052王洋607013012345学号姓名数学外语学号姓名数学外语总分1234512345(a)无序表(b)按学号排列的有序表(c)按
3、数学成绩排列的有序表(d)按总分成绩排列的有序表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刘大海8075
4、20042王伟908320066吴晓英828820038刘伟807020052王洋607012345学号姓名数学外语20052王洋607020038刘伟807020051刘大海807520066吴晓英828820042王伟9083学号姓名数学外语12345(e)按数学成绩排列的有序表不稳定的排序3.内部排序(内排序)----指待排序文件不大，一次可以在内存中完成的排序。即在排序进行的过程中不使用计算机外部存储器的排序过程。排序速度快。外部排序(外排序)----指待排序文件较大，文件存放在外存上，不能一次
5、调入内存的排序。即在排序进行的过程中需要对外存进行访问的排序过程。排序速度慢。本章主要讨论各种内部排序的方法。4.待排序的记录和顺序表(文件)的数据类型#defineMAXSIZE20//最大长度typedefintKeyType；//关键字类型typedefstruct//记录类型{KeyTypekey；//关键字InfoTypeotherinfo；//其它数据类型}RecType；//记录类型名typedefstruct{RecTyper[MAXSIZE+1]；//r[0]用作监视哨intlengt
6、h;//实际表长}SeqList；//记录表类型或表和表长分别定义和说明RecTyper[MAXSIZE+1]；//r[0]用作监视哨intlength；//实际表长5.排序算法分析(1)时间复杂度对n个记录排序，所需比较关键字的次数；最好情况；最坏情况；平均情况对n个记录排序，所需移动记录的次数；最好情况；最坏情况；平均情况(2)空间复杂度排序过程中，除文件中的记录所占的空间外，所需的辅助存储空间的大小。6.内排序方法(1)对顺序表的排序插入排序：直接插入排序；折半插入排序；2-路插入排序；表插入排序
7、；希尔(Shell)排序；交换排序：冒泡排序：单向冒泡排序，双向冒泡排序快速排序选择排序：简单选择排序；树形选择排序；堆排序归并排序2-路归并排序k-路归并排序基数排序多关键字排序最高位优先法最低位优先法链式基数排序(2)对单链表的排序直接插入,简单选择,冒泡排序,基数排序DonaldErvinKnuth高德纳（1938-）斯坦福大学教授1974年图灵奖得主《计算机程序设计的艺术》TheArtofComputerProgramming第一卷：基本算法1968第二卷：半数字化算法1969第三卷：排序与搜索
8、1973第四卷：组合算法《计算机与排版》TEX排版软件《超现实数》《具体数学》《作文式程序设计》10.2插入排序算法基本思想将待排序的记录插入到已排序的子文件中去，使得插入之后得到的子文件仍然是有序子文件。插入一个记录，首先要对有序子文件进行查找，以确定这个记录的插入位置。按查找方式的不同，插入排序又可以分为线性插入排序和折半插入排序，前者使用顺序查找，后者使用折半查找。1.直接插入排序(线性插入排序)设待排序的文件为：(r[1],r[2]
