数结 华中科技大学 计犷机学院(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
5.排序算法分析 (1)时间复杂度 ●对n个记录排序,所需比较关键字的次数; 最好情况;最坏情况;平均情况 ●对n个记录排序,所需移动记录的次数; 最好情况;最坏情况;平均情况 (2)空间复杂度 排序过程中,除文件中的记录所占的空间外, 所需的辅助存储空间的大小。 6.内排序方法 (1)对顺序表的排序 ●插入排序:直接插入排序; 折半插入排序;2-路插入排序;表插入排序; 希尔(She11)排序; ●选择排序:简单选择/选择排序; 树形选择排序;堆排序
5.排序算法分析 (1)时间复杂度 ● 对n个记录排序，所需比较关键字的次数； 最好情况；最坏情况；平均情况 ● 对n个记录排序，所需移动记录的次数； 最好情况；最坏情况；平均情况 (2)空间复杂度 排序过程中，除文件中的记录所占的空间外， 所需的辅助存储空间的大小。 6.内排序方法 (1)对顺序表的排序 ● 插入排序：直接插入排序； 折半插入排序；2-路插入排序；表插入排序； 希尔(Shell)排序； ● 选择排序：简单选择/选择排序； 树形选择排序；堆排序
●归并排序 2-路归并排序 k-路归并排序 ●交换排序 冒泡排序:单向冒泡排序,双向冒泡排序 快速排序 ●基数排序 多关键字排序 最高位优先法 最低位优先法 链式基数排序 (2)对单链表的排序 直接插入,简单选择,冒泡排序,基数排序
● 归并排序 2-路归并排序 k-路归并排序 ● 交换排序 冒泡排序：单向冒泡排序，双向冒泡排序 快速排序 ● 基数排序 多关键字排序 最高位优先法 最低位优先法 链式基数排序 (2)对单链表的排序 直接插入,简单选择,冒泡排序,基数排序
10.2插入排序 算法基本思想 将待排序的记录插入到已排序的子文件中去,使得插入之后 得到的子文件仍然是有序子文件。插入一个记录,首先要对有序 子文件进行査找,以确定这个记录的插入位置。按查找方式的不 同,插入排序又可以分为线性插入排序和折半插入排序,前者使 用顺序查找,后者使用折半査找。 1.直接插入排序(线性插入排序) 设待排序的文件为(r[1],r[2],,r[n]) 关键字为(r[1].key,r[2].key,,r[n].key) 首先,将初始文件中的记录r[1]看作有序子文件; 第1遍:将r[2]插入有序子文件中:若r[2].key<r[1].key 则r[2]插在r[1]之前;否则,插在r[1的后面。 第2遍:将记录r[3]插入前面已有2个记录的有序子文件中, 得到3个记录的有序子文件 以此类推,依次插入r[4],.,r[n],最后得到n个记录的递 增有序文件
10.2 插入排序 算法基本思想 将待排序的记录插入到已排序的子文件中去，使得插入之后 得到的子文件仍然是有序子文件。插入一个记录，首先要对有序 子文件进行查找，以确定这个记录的插入位置。按查找方式的不 同，插入排序又可以分为线性插入排序和折半插入排序，前者使 用顺序查找，后者使用折半查找。 1.直接插入排序(线性插入排序) 设待排序的文件为(r[1],r[2],...,r[n]) 关键字为(r[1].key,r[2].key,...,r[n].key) 首先,将初始文件中的记录r[1]看作有序子文件； 第1遍：将r[2]插入有序子文件中：若r[2].key<r[1].key， 则r[2]插在r[1]之前；否则，插在r[1]的后面。 第2遍：将记录r[3]插入前面已有2个记录的有序子文件中， 得到3个记录的有序子文件。 以此类推，依次插入r[4],...,r[n],最后得到n个记录的递 增有序文件
例.直接插入排序,设K0为"监视哨” KO Kl K2 K3 K4 K5 K6 初始关键字 43)2189154328 (43后移) 第1遍(趟)排序后:21(2143)89154328 (不后移) 第2遍排序后:89(214389)154328 (89,43,21后移) 第3遍排序后 15(15214389)4328 (89后移) (89,43,43后移)43(1521434389)28 第4遍排序后:4 第5遍排序后:28(152128434389)
例. 直接插入排序, 设K0为"监视哨” K0 K1 K2 K3 K4 K5 K6 初始关键字： ( 43 ) 21 89 15 43 28 (43后移) ┌─┘ ↓ 第1遍(趟)排序后：21 ( 21 43 ) 89 15 43 28 (不后移) │ ↓ 第2遍排序后： 89 ( 21 43 89 ) 15 43 28 (89,43,21后移) ┌──────┘ ↓ 第3遍排序后： 15 ( 15 21 43 89 ) 43 28 (89后移) ┌─┘ ↓ 第4遍排序后： 43 ( 15 21 43 43 89 ) 28 (89,43,43后移) ┌──────┘ ↓ 第5遍排序后： 28 ( 15 21 28 43 43 89)
直接插入排序算法 void InsertSort (RecType r[, int n) //对数组r[1.n]中的n个记录作插入排序 I int i, j for(i=2; i=n: i++) r[0]=r[i]; //待插记录r[订]存入监视哨中 j=i-1 //从r[i1]开始向左扫描 while(rlo]. key<rLj]. key) r[j+1]=r[j; //记录后移 /继续向左扫描 r[j+1]=r[0]; //插入记录r[0],即原r[i]
直接插入排序算法 void InsertSort(RecType r[],int n） // 对数组r[1..n]中的n个记录作插入排序 { int i,j； for (i=2；i<=n；i++) { r[0]=r[i]； //待插记录r[i]存入监视哨中 j=i-1； //从r[i-1]开始向左扫描 while(r[0].key<r[j].key) { r[j+1]=r[j]； //记录后移 j--； //继续向左扫描 } r[j+1]=r[0]； //插入记录r[0],即原r[i] } }