第8章排序 8.1 插入排序《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

学科网 第8章内部排序 8.1概述 8.2插入排序 8.3交换排序 8.4选择排序 8.5归并排序 6学科网 WWw.ZXXK.COM 8.1 概述 1.什么是排序？ 将一组杂乱无章的数据按一定的规律顺次排列起来。 存放在数据表中 按关鍵字排序 定义：设有记录序列：{R1、R2 Rn}其 相应的关键字序列为：【K1、K2...Kn};若 存在一种确定的关系：Kx<=Ky<=.<=Kz则将 记录序列{R1、R2 Rn}排成按该关键 字有序的序列：{Rx、Ry Rz}的操作 称之为排序。 6学科网 WWw.ZXXK.COM 2.排序的目的是什么？一一便于查找！ 3.株序算法的好坏如何衡量？ 时间效率一一 排序速度（即排序所花费的全部比较次数） 空间效率一一占内存辅助空间的大小 稳定性一一若两个记录A和B的关键字值相等，但排序后A、B 的先后次序保持不变，则称这种排序算法是稳定的。 学科网 4.什么叫内部排序？什么叫外部排序？ Www.ZXXK.COM 若待排序记录都在内存中，称为内部排序 若待排序记录一部分在内存，一部分在外存，则 称为外部排序。 注：外部排序时，要将数据分批调入内存来排序，中间 结果还要及时放入外存，显然外部排序要复杂得多。 大多数排序算法都有两个基本的操作 (1)比较两个关键字的大小 (2)将记录从一个位置移动到另一个位置 记录序列的存储方式： (1)顺序存储（2) 静态链表 （3)地址 o6学科网 6.顺序存诸 (顺序表)的抽象数据类型如何表示？ 注：大多数排序算法都是针对顺序表结构的便于直接移动元素) define MAXSIZE 20 /设记录不超过20个 typedef int KeyType; /设关键字为整型量 (int型) Typedef struct /定义每个记录（数据元素）的结 构 KeyType key /关键字 InfoType otherinfo; /其它数据项 Typeder ct /定义顺序表的结构 RecordType r[MAXSIZE+1];/存储顺序表的向量 /r[0]一般作哨兵或缓冲区 int length /顺序表的长度 SqList 6学科网 7.内部排序的算法有哪些？ WWw.ZXXK.COM 按排序的规则不同，可分为5类 插入排序 交换排序 (重点是快速排序) 选择排序 归并排序 基数排序 按排序算法的时间复杂度不同，可分为3类： ●简单的排序算法：时间效率低，O(n2) ●先进的排序算法：」 时间效率高，O(nlog2n) ·基数排序算算法：时间效率高，O(dXn) d=关键字的位数（长度） 6学科网 8.2插入排序 Www.ZXXK.COM 插入排序的基本思想是： 每步将一个待排序的对象，按其关键码大小， 插入到前面已经排好序的一组对象的适当位置上，直 到对象全部插入为止。 简言之，边插入边排序， 保证子序列中时都是排好序的。 插入排序有多种具体实现算法： 1)直接插入排序 2)折半插入排序 3) 希尔排序 1)直接插入排序 最简®o折科网 法！ 新元素插入到哪里？ 在已形成的有序表中线性查找，并 在适当位置插入，把原来位置上的元素向后顺移。 例1：关键字序列T=(13,6,3,31,9,27,5,11), 请写出直接插入排序的中间过程序列。 【13】,63,31,9,27,5, 11 【6,13】,3,31,9,27,5, 11 【3,6,13】,31,9,27,5, 11 【3,6,13,31】,9,27,5, 11 【3,6,9,13,31】,27,5, 11 6学科网 例2：关键字序列T=( 21,25,49,25 WW.ZXXK.Co 16,08) 请写出直接插入排序的具体实现 表示后一个 解：假设该序列已存入一维数组V[7]中， 将VO]为缓冲或 暂存单元(Temp)。则程序执行过程为： 初态 16 21 25 2549 08 08 0 1 2 3 4 5 6 完成！ i= i= i- 1 2 4 =5 直接插入排序的演示 6学科网 Www.ZXXK.COM void Insertsort(SqList *l) int i,j; for(i=2;i<=l->length;i++) {->r[o]=l->r[i] j=i-1; while(I->r[0].key<l->r[j].key) {->r[j+1]=l->r[]; j--i } >r[j+1]=l->r[0] } }