Open ssfc opened 6 years ago
46.Ep 41: 排序的定义; 内部排序, 不需要访问外存, 否则就是外部排序; 内部排序的方法, 逐步扩大记录的有序序列长度; 插入类, 将无序子序列中的一个或几个记录插入到有序序列中, 从而增加记录的有序子序列的长度; 交换类; 选择类; 归并类; 一趟插入排序; 直接插入排序; 实现排序的基本操作, 比较和移动; 对于直接插入排序, 最好的情况n-1, 最坏的情况n^2; 折半插入排序; 表插入排序, 表插入的过程; (2018-5-6) 47.Ep 42: void LInsertSort(); void Arrange(); 希尔排序; void ShellInsert(); void ShellSort(); 快速排序; 冒泡排序; void BubbleSort(); 比较n^2, 移动n^2; 一趟快速排序; int Partition(); 快速排序是递归; 简单选择排序; (2018-5-6) 48.Ep 43: 堆排序; 堆的定义; 堆排序是利用堆的特性对记录序列进行排序; 筛选, 对左右均为堆的完全二叉树, 调整根节点使整个二叉树为堆; void HeapSort(); 堆排序的时间复杂度, nlogn; 归并排序; void Merge(); 2路归并排序; void Msort(); void MergeSort(); 多关键字排序; 实现多关键字排序, 最高位优先MSD法, 最低位优先LSD法; (2018-5-6) 49.Ep 44: 链式基数排序; 分配-收集的方法; review; O(nlogn), 快速排序, 堆排序, 归并排序; O(n^2), 直接插入排序, 冒泡排序, 简单选择排序; O(n), 基数排序; 当排序记录序列按关键字有序, 直接排序和起泡排序O(n), 快速排序为O(n^2); 空间性能; 所有的简单排序方法和堆排序的空间复杂度为O(1), 快速排序为O(logn), 归并排序为O(n), 链式基数排序为O(rd); 排序方法的稳定性能, 两个关键字相等的记录在排序后顺序不变; 多关键字LSD, 必须采用稳定; 快速排序, 堆排序, 希尔排序不稳定; 基于比较关键字的排序算法时间下限是O(nlogn), 从判定树可以证明; review; 外部排序, 记录数量很大内存不够; 外部排序的基本过程, 构造若干有序子序列, 通过归并, 逐步扩大有序子序列的长度; (2018-5-6) 50.Ep 45: m段k路, 则次数logk(m); 文件, 记录的集合; 操作系统的文件, 数据库文件; 文件的逻辑结构, 物理结构; 检索, 顺序存取, 直接存取; 顺序文件的组织形式, 连续文件, 串联文件; 便于顺序存取, 不便于直接存取, 插入新的记录只能在末尾, 删除记录只作标记, 更新必须生成新的文件; 批处理方式, 主文件, 事务文件; 每个操作判别合法性, 对于一个记录存在多个操作; 索引文件; 主文件和多级索引; 关键字和指针; 主文件无序索引有序; 索引在输入数据建立文件自动生成; 操作的特点; 索引文件的结构; 多级静态索引, 动态索引; 索引表采用查找树表或哈希表; (2018-5-10) 51.Ep 46: 索引顺序文件; ISAM文件; 文件的组织方式, 磁道索引, 柱面索引, 主索引; 检索, 顺序存取, 按关键字存取; 删除, 作删除标记; VSAM文件; 控制区间(逻辑磁道), 控制区域(逻辑柱面); 顺序集是单链表, 索引集的结点是B+树的非叶结点; 文件的操作, 检索, 插入, 删除; VSAM文件通常作为大型索引顺序文件的标准组织方式, 优点动态分配和释放, 缺点占用较多存储空间; 直接存取文件, 直接得到映像地址; 哈希文件的结构; 文件的操作, 检索, 插入, 删除; 优点, 无需排序; (2018-5-10) 52.Ep 47: 多关键字文件; 主索引, 次索引; 次索引的组织方法, 多重链表文件; 倒排文件; review; example 9.15; example 9.5, 二叉排序树及其平均查找长度; example 9.18; example 9.13; (2018-5-10) 53.Ep 48: example 10.4, 快速排序最好情况; example 10.9; example 10.17; example 11.1; (2018-5-10)
46.Ep 41: 排序的定义; 内部排序, 不需要访问外存, 否则就是外部排序; 内部排序的方法, 逐步扩大记录的有序序列长度; 插入类, 将无序子序列中的一个或几个记录插入到有序序列中, 从而增加记录的有序子序列的长度; 交换类; 选择类; 归并类; 一趟插入排序; 直接插入排序; 实现排序的基本操作, 比较和移动; 对于直接插入排序, 最好的情况n-1, 最坏的情况n^2; 折半插入排序; 表插入排序, 表插入的过程; (2018-5-6) 47.Ep 42: void LInsertSort(); void Arrange(); 希尔排序; void ShellInsert(); void ShellSort(); 快速排序; 冒泡排序; void BubbleSort(); 比较n^2, 移动n^2; 一趟快速排序; int Partition(); 快速排序是递归; 简单选择排序; (2018-5-6) 48.Ep 43: 堆排序; 堆的定义; 堆排序是利用堆的特性对记录序列进行排序; 筛选, 对左右均为堆的完全二叉树, 调整根节点使整个二叉树为堆; void HeapSort(); 堆排序的时间复杂度, nlogn; 归并排序; void Merge(); 2路归并排序; void Msort(); void MergeSort(); 多关键字排序; 实现多关键字排序, 最高位优先MSD法, 最低位优先LSD法; (2018-5-6) 49.Ep 44: 链式基数排序; 分配-收集的方法; review; O(nlogn), 快速排序, 堆排序, 归并排序; O(n^2), 直接插入排序, 冒泡排序, 简单选择排序; O(n), 基数排序; 当排序记录序列按关键字有序, 直接排序和起泡排序O(n), 快速排序为O(n^2); 空间性能; 所有的简单排序方法和堆排序的空间复杂度为O(1), 快速排序为O(logn), 归并排序为O(n), 链式基数排序为O(rd); 排序方法的稳定性能, 两个关键字相等的记录在排序后顺序不变; 多关键字LSD, 必须采用稳定; 快速排序, 堆排序, 希尔排序不稳定; 基于比较关键字的排序算法时间下限是O(nlogn), 从判定树可以证明; review; 外部排序, 记录数量很大内存不够; 外部排序的基本过程, 构造若干有序子序列, 通过归并, 逐步扩大有序子序列的长度; (2018-5-6) 50.Ep 45: m段k路, 则次数logk(m); 文件, 记录的集合; 操作系统的文件, 数据库文件; 文件的逻辑结构, 物理结构; 检索, 顺序存取, 直接存取; 顺序文件的组织形式, 连续文件, 串联文件; 便于顺序存取, 不便于直接存取, 插入新的记录只能在末尾, 删除记录只作标记, 更新必须生成新的文件; 批处理方式, 主文件, 事务文件; 每个操作判别合法性, 对于一个记录存在多个操作; 索引文件; 主文件和多级索引; 关键字和指针; 主文件无序索引有序; 索引在输入数据建立文件自动生成; 操作的特点; 索引文件的结构; 多级静态索引, 动态索引; 索引表采用查找树表或哈希表; (2018-5-10) 51.Ep 46: 索引顺序文件; ISAM文件; 文件的组织方式, 磁道索引, 柱面索引, 主索引; 检索, 顺序存取, 按关键字存取; 删除, 作删除标记; VSAM文件; 控制区间(逻辑磁道), 控制区域(逻辑柱面); 顺序集是单链表, 索引集的结点是B+树的非叶结点; 文件的操作, 检索, 插入, 删除; VSAM文件通常作为大型索引顺序文件的标准组织方式, 优点动态分配和释放, 缺点占用较多存储空间; 直接存取文件, 直接得到映像地址; 哈希文件的结构; 文件的操作, 检索, 插入, 删除; 优点, 无需排序; (2018-5-10) 52.Ep 47: 多关键字文件; 主索引, 次索引; 次索引的组织方法, 多重链表文件; 倒排文件; review; example 9.15; example 9.5, 二叉排序树及其平均查找长度; example 9.18; example 9.13; (2018-5-10) 53.Ep 48: example 10.4, 快速排序最好情况; example 10.9; example 10.17; example 11.1; (2018-5-10)