数结 华中科技大学 计犷机学院(11) 200=g=
2001 -- 12 --31 华中科技大学 数据结构计算机学院(11)
第十章内排序 10.1概述 1.排序—将文件或表中的记录,通过某种方法整理成按关 键字大小次序排列的处理过程。 假定n个记录的文件为 对应的关键字为 (K1,K K) 则排序是确定如下一个排列 p1, p 使得 Kp1≤K2≤...≤K1 从而得到一个有序文件
第十章 内排序 10.1 概述 1.排序----将文件或表中的记录，通过某种方法整理成按关 键字大小次序排列的处理过程。 假定n个记录的文件为 (R1,R2,...,Rn) 对应的关键字为 (K1,K2,...,Kn) 则排序是确定如下一个排列 p1,p2,...,pn 使得 Kp1≤Kp2≤...≤ Kpn 从而得到一个有序文件 (Rp1,Rp2,...Rpn)
学生成绩表 学号姓名数学外语 学号姓名数学外语 120051刘大海8075 120038刘伟8070 2[20024王伟90832[2002王伟9083 20066 吴晓英82|B-2051刘大海8075 4[20084刘伟80704[2002王洋‖6070 52002王洋607052006吴晓英828 (a)无序表 (b)按学号排列的有序表 学号姓名数学外语 学号姓名数学外语总分 202王洋「60012002伟90831173 2|20051刘大海80752006吴晓英」82|881170 3[2003刘伟8070 200511刘大海8075155 4[2006吴晓英82|884[2008刘伟8o70150 520042王伟9083520052王洋6070130 (c)按数学成绩排列的有序表 (d)按总分成绩排列的有序表
学生成绩表 20051 刘大海 80 75 20042 王 伟 90 83 20066 吴晓英 82 88 20038 刘 伟 80 70 20052 王 洋 60 70 1 2 3 4 5 学 号 姓 名 数学 外语 20038 刘 伟 80 70 20042 王 伟 90 83 20051 刘大海 80 75 20052 王 洋 60 70 20066 吴晓英 82 88 学 号 姓 名 数学 外语 20052 王 洋 60 70 20051 刘大海 80 75 20038 刘 伟 80 70 20066 吴晓英 82 88 20042 王 伟 90 83 20042 王 伟 90 83 173 20066 吴晓英 82 88 170 20051 刘大海 80 75 155 20038 刘 伟 80 70 150 20052 王 洋 60 70 130 1 2 3 4 5 学 号 姓 名 数学 外语 学 号 姓 名 数学 外语 总分 1 2 3 4 5 1 2 3 4 5 (a) 无序表 (b) 按学号排列的有序表 (c) 按数学成绩排列的有序表 (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,2,42,25,30,18)不稳定的排序(10,18,2,25,25,30,42) 学号姓名数学外语 学号姓名数学外语 120051刘大海8075 20052王洋6070 2|20024王伟9083不稳定2120084刘伟8070 200吴晓英828的排序82051刘大海8075 420038刘伟80 420066吴晓英8288 520052王洋6070 20042王伟9083 (e)按数学成绩排列的有序表
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 刘大海 80 75 20042 王 伟 90 83 20066 吴晓英 82 88 20038 刘 伟 80 70 20052 王 洋 60 70 1 2 3 4 5 学 号 姓 名 数学 外语 20052 王 洋 60 70 20038 刘 伟 80 70 20051 刘大海 80 75 20066 吴晓英 82 88 20042 王 伟 90 83 学 号 姓 名 数学 外语 1 2 3 4 5 (e) 按数学成绩排列的有序表 不稳定 的排序
3.内部排序(内排序)——在计算机内存中进行的排序 外部排序(外排序)-—借助计算机外存进行的排序 4.待排序的记录和顺序表(文件)的数据类型 #define maXsize 20 //最大长度 typedef int Key Type;/)关键字类型 typedef struct //记录类型 i Key type key //关键字 InfoType otherinfo;/其它数据类型 I Rectype; //记录类型名 typedef struct RecType r[ MAXSIZE+1];//r[0]用作监视哨 int length //实际表长 length<MAXSIZE J SeqList; //表和表长合并为 Seqlist 或: //表和表长分别定义和说明 RecType r LMAXSIZE+1];/r[0]用作监视哨 int length: //实际表长 length< MAXSIZE
3.内部排序(内排序)----在计算机内存中进行的排序 外部排序(外排序)----借助计算机外存进行的排序 4.待排序的记录和顺序表(文件)的数据类型 #define MAXSIZE 20 //最大长度 typedef int KeyType； //关键字类型 typedef struct //记录类型 { KeyType key； //关键字 InfoType otherinfo； //其它数据类型 }RecType； //记录类型名 typedef struct { RecType r[MAXSIZE+1]；//r[0]用作监视哨 int length； //实际表长length≤MAXSIZE }SeqList； //表和表长合并为SeqList 或： //表和表长分别定义和说明 RecType r[MAXSIZE+1]； //r[0]用作监视哨 int length； //实际表长length≤MAXSIZE