《严蔚敏数据结构 (16)》-(课件).ppt

数据结构课程的内容 第10章 内部排序 10.1 概述 4. 什么叫内部排序？什么叫外部排序？ 6. 顺序存储（顺序表）的抽象数据类型如何表示？ 7. 内部排序的算法有哪些？ 10.2 插入排序 1) 直接插入排序 直接插入排序算法的实现： 例1：关键字序列T= （21，25，49，25*，16，08），请写出直接插入排序的具体实现过程。 2） 折半插入排序（自学） 3） 2-路插入排序（自学） 4）表插入排序（自学） 例：关键字序列 T=(21，25，49，25*，16，08）， 请写出表插入排序的具体实现过程。 表插入排序的算法（自学） 表插入排序算法分析： 5）希尔（shell）排序 例：关键字序列 T=(49，38，65，97, 76, 13, 27, 49*，55, 04），请写出希尔排序的具体实现过程。 时间效率： 原始序列： 256，301，751，129，937，863，742，694，076，438 希尔排序算法（其中某一趟的排序操作） 对前页程序中间for循环的理解： 10.3 交换排序 1) 冒泡排序 冒泡排序的算法分析 * 10.1 概述 10.2 插入排序 10.3 交换排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 1. 什么是排序？ 将一组杂乱无章的数据按一定的规律顺次排列起来。 2. 排序的目的是什么？ 存放在数据表中 按关键字排序 3.排序算法的好坏如何衡量？ 时间效率——排序速度（即排序所花费的全部比较次数） 空间效率——占内存辅助空间的大小 稳定性——若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。 ——便于查找！ ——若待排序记录都在内存中，称为内部排序； ——若待排序记录一部分在内存，一部分在外存，则称为外部排序。 注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。 5.待排序记录在内存中怎样存储和处理？ ① 顺序排序——排序时直接移动记录； ② 链表排序——排序时只移动指针； ③ 地址排序——排序时先移动地址，最后再移动记录。 注：地址排序中可以增设一维数组来专门存放记录的地址。 注：大多数排序算法都是针对顺序表结构的(便于直接移动元素) Typedef struct { //定义每个记录（数据元素）的结构 KeyType key ; //关键字 InfoType otherinfo; //其它数据项 }RecordType，node ; //例如node.key表示其中一个分量 Typedef struct { //定义顺序表L的结构 RecordType r [ MAXSIZE +1 ]; //存储顺序表的向量 //r[0]一般作哨兵或缓冲区 int length ; //顺序表的长度 }SqList ,L; //例如L.r或L.length表示其中一个分量 # define MAXSIZE 20 //设记录数不超过20个（本章都如此假设） typedef int KeyType ; //设关键字为整型量（int型） 若r数组是表L中的一个分量且为node类型， 则r中某元素的key分量表示为：r[i].key 在我们的实验中完全可以写为 (因为很多同学看不懂)： int r [ MAXSIZE +1 ]，length; 或：typedef struct{ int r [ MAXSIZE +1 ]; int length;}SqList ,L； ——按排序的规则不同，可分为5类： 插入排序 交换排序（重点是快速排序） 选择排序 归并排序 基数排序 d＝关键字的位数(长度) ——按排序算法的时间复杂度不同，可分为3类（参见教材P289） 简单的排序算法：时间效率低，O(n2) 先进的排序算法: 时间效率高，O( nlog2n ) 基 数 排 序 算法：时间效率高，O( d×n) 插入排序的基本思想是： 插入排序有多种具体实现算法： 1) 直接插入排序 2) 折半插入排序 3）2-路插入排序 4) 表插入排序 5) 希尔排序 每步将一个待排序的对象，按