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