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