排序_计算机数据结构考研
2020-07-07 13:38:49 0 举报AI智能生成
排序_计算机数据结构考研
作者其他创作
大纲/内容
版权∈ 本人所有
严禁擅自转载和商用 受法律保护
严禁擅自转载和商用 受法律保护
更新记录
2020.6.6开坑
排序
基本概念
分类
内部排序
数据都存在内存内【关注降低空间复杂度】
外部排序
数据太多 无法全部存入内存【关注降低磁盘读写次数】
类型
内部排序
插入排序
每次将待排序的记录按照关键字大小插入已排序的子序列中
空间O(1) 时间O(n²) 稳定算法
空间O(1) 时间O(n²) 稳定算法
优化——折半插入排序 & 链表法
Both比较关键字次数减少 时间复杂度O(n²)
Both比较关键字次数减少 时间复杂度O(n²)
希尔排序Shell
分割成若干子表 对子表直接插入排序 再逐步缩小增量d至1
代码实现
空间O(1) 时间O(n^1.3）
不稳定算法 仅适用顺序表 不适用链表
空间O(1) 时间O(n^1.3）
不稳定算法 仅适用顺序表 不适用链表
冒泡排序
两两对比排序 每次交换都需要移动3次元素
算法稳定 空间O(1) 时间O(n²) 适用顺序表、链表
算法稳定 空间O(1) 时间O(n²) 适用顺序表、链表
选择排序
简单选择排序
每一趟在待排序内选取关键字最小的元素
空间O((1) 时间O(n²) 算法不稳定 适用顺序表、链表
空间O((1) 时间O(n²) 算法不稳定 适用顺序表、链表
堆 Heap
分类
大根堆(大顶堆)【顺序储存的完全二叉树 根≥左、右】
关键字序列L 满足L(i)≥L(2i)且L(i)≥L(2i+1) i∈[1,n/2]
建立大根堆
建立大根堆
大根堆排序代码 不稳定算法 最后得到递增序列
一个结点每下坠一层最多比较2次关键字【排序】 关键字对比不超过4次【建堆】
完全二叉树树高log2n+1 空间O(1)
时间O(n)【建堆】+O(nlog2n)【排序】=O(nlog2n)
一个结点每下坠一层最多比较2次关键字【排序】 关键字对比不超过4次【建堆】
完全二叉树树高log2n+1 空间O(1)
时间O(n)【建堆】+O(nlog2n)【排序】=O(nlog2n)
小根堆(小顶堆)【顺序储存的完全二叉树 根≤左、右】
关键字序列L 满足L(i)≤L(2i)且L(i)≤L(2i+1) i∈[1,n/2]
最后得到递减序列
基本操作
插入
小根堆
新元素放在表尾 与父节点对比 若新元素＜父节点 则二者互换【最需对比1次关键字】
删除
小根堆
被删除元素代替堆底元素 然后让元素不断下坠【最多对比2次关键字】
基数排序 Radix
以二路为例子
第一趟以个位分配挂链表
第二趟按需收集挂链
第二趟以十位分配挂链表
第四趟按需收集挂链
··· ····
应用
年月日年龄递增减
归并排序
把两个或多个已经有序的序列合并
算法稳定
二路归并为例
算法稳定
二路归并为例
排序代码实现 空间O(n)由辅助数组B决定
n个元素进行2路归并排序 归并趟数log2n
每趟时间O(n) 则最终算法时间O(nlog2n)
n个元素进行2路归并排序 归并趟数log2n
每趟时间O(n) 则最终算法时间O(nlog2n)
外部排序
数组交换
磁盘读写以'块'为单位
数据读入内存才修改
修改完了要写回磁盘
数据读入内存才修改
修改完了要写回磁盘
做法【以二路归并为例】
生成初始归并段
读写各16次 仍需内部排序
读写各16次 仍需内部排序
第一趟归并
读写各16次 仍需内部排序
读写各16次 仍需内部排序
第二趟归并
读写各16次 仍需内部排序
读写各16次 仍需内部排序
第三趟归并
读写各16次 仍需内部排序
读写各16次 仍需内部排序
时间开销
读写外存时间 + 内部排序所需时间 + 内部归并所需时间
优化
对于r个初始归并段 做k路归并 则归树可用k叉树表示
若树高为h 则归并趟数=h-1=logkr
若树高为h 则归并趟数=h-1=logkr
增多路归并可来减小归并趟数
代价
需增加相应的输入缓冲区 增大空间开销【置换-选择排序】
需增大内部排序开销 增多关键字对比次数【败者树解决】
增加初始归并段长度 则可减小初始归并段数量r
败者树
可视为完全二叉树 (多了一个头头)
非叶子结点记录左右子树中的失败者
胜利者继续上升比较
非叶子结点记录左右子树中的失败者
胜利者继续上升比较
对于k路归并 第一次构造败者树 关键字需对比k-1次
有了败者树 选出最值元素 关键字需对比log2k次
有了败者树 选出最值元素 关键字需对比log2k次
置换-选择排序
算法思想
最佳归并树
求 磁盘读写次数最少 就是归并树带权路径长度WPL最小 —— 哈夫曼树
若 k叉归并中初始归并树无法构造严格k叉归并树 则需要补充几个长度为0的虚段
章节技巧
0 条评论
下一页
