首页  思维导图  详情

DS-8-排序

2021-08-04 21:00:22   7  举报





AI智能生成

为你推荐

查看更多



数据结构第八章排序知识点整理庆祝DS复习完了，免费发持续更新

数据结构

考研

计算机

排序

大学教育

作者其他创作

大纲/内容

将两个有序序列合并

2路归并

每次都在n个元素中选择最小的插入序列

需要至少对比n-1次

将n个有序序列合并

n路归并

基本概念

MergeSort(low，mid)

MergeSort(mid+1，high)

MergeSort(low，high)//递归实现

实现

对n个元素进行2路归并，需要归并趟

每趟都要计算所有元素

含有n个结点的二叉树必有层

分析归并复杂度

归并树(倒二叉树)

辅助数组n

递归工作栈logn<n

空间复杂度O(n)

共要归并趟

对比次数n-1

移动元素2n

每一趟对n个元素归并都要消耗线性时间

时间复杂度O()

稳定性：稳定

性能分析

归并排序

按顺序形成新表

按最低位分配到表中

按次低位分配到链表中

……

按顺序形成有序表

按最高位分配到链表中

越优先的位越靠后进行分配

r为关键字可能取值数

空间复杂度O(r)

时间复杂度O(nr)

数据关键字可以方便地拆分为d组，且d较小

每组关键字的取值范围不大，r较小

数据元素规模n较大

应用

d=3

n可以很大

年月日排序

r非常大

n很大

对中文人名排序

反例

基数排序

OS以块为单位操作磁盘存储的数据

内存中开辟一块缓冲区，再读取一块

读磁盘

需要把内存中的数据整块地写回磁盘块

写磁盘

内存外存间数据交换

外部数据太多，无法一次性全部读入内存

最少只需3块大小的缓冲区即可对任意大小数据进行排序

共需要趟归并

一趟排序归并段长度翻k倍，数量减至1/k

使用归并排序

2n块数据，需要2n次读和2n次写

两块读入内存，可构造一个初始归并段

存在空的输入缓冲区时，不允许向输出缓冲区写入数据但可以将满输出缓冲区写回磁盘

清空输出缓冲区，并继续归并，当其中一个输入缓冲区空时，立即读入它存储的归并段的下一块

重复上述两步，直到两个归并段被归并为新的归并段

重复以上3步，直到所有段被归并为1段

外部排序原理

少

内部排序时间+内部归并时间

每一趟都要IO次

读写外存时间

时间开销

影响效率的因素

置换-选择排序

受限于内存工作区大小

增大初始归并段，减少初始归并段的数量

最多只能有k个段归并为1个段

每一趟归并中，若有m个归并段参与归并，则这一趟处理生成了个新归并段

k路平衡归并

缓冲区越多，总容量越大，归并段生长越快，趟数越少

缓冲区越多，内存开销越大，每挑出一个元素对比次数增加，内部归并时间增加

多路归并

优化思路

外部排序

n个元素构建的败者树中，每选出一个新的最小元素，最多只需要对比次

叶子结点(虚拟的)对应待比较元素，非根结点存储两个子结点中比较的败者，根结点只有一个子结点

每个结点对应一次比较，每层结点对应一轮比较

败者树

先读满工作区，输出一个最小的作为第一归并段首位，并记录其值

当工作区满时，输出工作区中最小且大于记录的到当前归并段，并记录其值

当工作区不满时，读入一个元素，除非无元素可以读入

当工作区满且无可以输出的数时，当前归并段结束，清除记录并输出一个最小的作为新的归并段，记录其值

工作区空时，结束当前的归并段构造任务

内存工作区采用如下工作方式

输出指的是输出到磁盘，但是实际过程中还包括输出缓冲区以及输出缓冲区满了才会输出到磁盘的过程

注

置换-选择排序生成的初始归并段长度可能不同

若每个叶结点的值为其块数，则读写次数等于2*结点值

每个非叶结点的值等于其子结点的值之和

可以据此计算整棵树所有叶结点的带权路径长度之和

IO次数=2WPL

最佳归并树就是WPL最小的归并方案

严格并非完全，只是每个非叶结点都必须有m个子结点

设初始归并段有个，需要补充个虚段，必须满足为整数

若初始归并段数量无法构成严格的m叉归并树，必须先补充长度为0的虚段直到可以构成严格m叉归并树

选最小的m个结点，并将其连在一个父结点上，用此父结点替代原有m个节点

重复上一步直到所有节点均被连接在树上

如有虚段，删除之

可以构造m路最佳归并树

构造

可见归并树就是m叉哈夫曼树

归并树不一定是完全二叉树

最佳归并树

时间复杂度

空间复杂度

对原序列关键字相同的元素，若经排序后其相对位置不变，则称该排序算法稳定，否则称不稳定

稳定性

性能指标

插入排序

交换排序

选择排序

内部排序

关注如何降低复杂度

额外关注降低硬盘读写次数

分类

数据是否都在内存内部

旧金山大学网站

将待排序记录按关键字大小插入前面已经排好的子序列中

for (j=i-1; j >= 0 && a[j]>temp; --j) a[j+1]=a[j];

a[j+1]=temp;

foreach a[i] in 待排if a[i]<a[i-1]

哨兵

优化

空间复杂度O(1)

n个关键字，第i个关键字最多对比i+1次，移动i+2次

直接插入排序

查找到相同元素仍要继续查找以保证稳定性

停止位置(LOW)及其右所有元素均要右移

插入到LOW的位置

比对数降低了但移动次数不变

折半插入排序

先追求部分有序，在实现全局有序

对子序列内部进行直接插入排序

其实增量序列间隔d不一定要折半，但是折半效率最高

减半d，重复以上两步，直到完成d=1的排序

经历的排序轮数越多，序列越接近严格有序

for (j=i-d; j >= 0 && a[j]>temp; j-=d) a[j+d]=a[j];

a[j+d]=temp;

for (i=d+1; i<.n; ++i) if(a[i]<a[i-d])

for (d = n/2; d >= 1; d /= 2)

时间复杂度O()以下，视n的取值最小可达O()

稳定性：不稳定

只适用于顺序表

希尔排序

前向/后向比较相邻元素的值，若为逆序则交换，将序列比较完，称为一趟

一趟排序会让关键字最大/最小的值排到正确位置上，因此每趟排序无需再比较上一趟末位

若一趟排序没有发生交换，则此时元素整体有序，可以提前终止

当一趟排序只包含最后两个元素时，完成后算法终止

每次交换要移动3次元素

最坏时(全逆序)每次对比都要交换

时间复杂度最坏/平均O() ，最好O(n)

可用于链表

冒泡排序

每趟都会令一个中间元素确定最终位置

即第n趟会确定个元素的位置

按照408定义，每一层算一趟排序

if a-b=1 return;

high--;

while *high≥pivot

*low=*high;

low++；

while *low<pivot

*high=*low；

while low≠high

*low=pivot;

空间复杂度O()

有序、逆序效率最差

枢轴越接近中位数，效率越高(树越平衡)

时间复杂度O() ~O()

例：221

快速排序

每趟在待排元素中选取关键字最大/小的元素加入有序子序列

对n个元素的简单选择排序只需要进行n-1趟(末元素无需排序)

性能发挥很稳定，不随序列变化

简单选择排序

(排序过程中)每趟在待排元素中选取关键字最大/小的元素加入有序子序列

大根堆：span class=\"equation-text\" data-index=\"0\" data-equation=\

小根堆：span class=\"equation-text\" data-index=\"0\" data-equation=\

结构

i的左孩子

2i+1

i的右孩子

floor(i/2)

i的父结点

或

i所在层

编号≤n

是否有xx

\\lfloor n/2\floor\" contenteditable=\"false\"

是否是叶子

二叉树的顺序存储

大根堆经过排序得到递增序列

小根堆经过排序得到递减序列

建堆不论大根堆还是小根堆均可

=;//另存结点值//筛选子结点for (k=2i;k<=len;k*=2){ //筛选较大关键字子结点 if (k<len && <) ++k; //调整结点关系 if (<){ =; //子结点关键字上浮 i=k;//钻入子结点 } else break;//满足规则结束调整}//循环结束时i已经指向下沉的终点=;//回填结点关键字

循环形式

=;//另存结点值//筛选较大关键字子结点let k=2i;if (k<len && <) ++k;//调整结点关系if (<){ =; //子结点关键字上浮 i=k;//钻入子结点 =;//回填结点关键字 Adjust();//钻入被调子结点}return;

尾递归形式

Adjust(a[i])

for (i=len/2; i>0;--i) Adjust(a[i]);

筛选法建堆

对于每个非叶子结点，都在其本身和其子结点组成的局部堆中构造符合要求的结构，谓之“筛选”

font color=\"#9E9E9E\

O()

插入元素

//被删元素用堆底元素替代，然后下坠该元素直到无法下坠a[this]=a[len]; --len; Adjust(this);

删除元素