首页  思维导图  详情

DS-8-排序

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





AI智能生成

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

数据结构

考研

计算机

排序

大学教育

作者其他创作

大纲/内容

归并排序

基本概念

2路归并

将两个有序序列合并

n路归并

将n个有序序列合并

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

需要至少对比n-1次

实现

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

MergeSort(low，mid)

MergeSort(mid+1，high)

Merge(low,mid,high)

归并树
(倒二叉树)

分析归并复杂度

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

每趟都要计算所有元素

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

性能分析

空间复杂度O(n)

辅助数组n

递归工作栈logn<n

时间复杂度O()

共要归并趟

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

对比次数n-1

移动元素2n

稳定性：稳定

基数排序

实现

按最低位分配到表中

按顺序形成新表

按次低位分配到链表中

按顺序形成新表

……

按顺序形成新表

按最高位分配到链表中

按顺序形成有序表

性能分析

空间复杂度O(r)

r为关键字可能取值数

时间复杂度O(nr)

稳定性：稳定

应用

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

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

数据元素规模n较大

反例

对中文人名排序

r非常大

n很大

外部排序

内存外存间数据交换

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

读磁盘

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

写磁盘

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

外部排序原理

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

使用归并排序

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

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

共需要趟归并

实现

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

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

两个归并段首块分别读入输入缓冲区1,2，对其
进行归并，当输出缓冲区满时立即写回磁盘

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

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

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

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

性能分析

影响效率的因素

时间开销

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

少

读写外存时间

每一趟都要IO次

优化思路

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

受限于内存工作区大小

置换-选择排序

多路归并

k路平衡归并

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

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

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

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

败者树

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

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

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

置换-选择排序

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

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

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

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

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

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

注

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

最佳归并树

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

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

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

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

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

IO次数=2WPL

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

构造

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

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

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

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

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

如有虚段，删除之

可以构造m路最佳归并树

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

基本概念

性能指标

时间复杂度

空间复杂度

稳定性

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

分类

内部排序

插入排序

交换排序

选择排序

归并排序

基数排序

外部排序

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

旧金山大学网站

插入排序

直接插入排序

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

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

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

a[j+1]=temp;

优化

哨兵

性能分析

空间复杂度O(1)

时间复杂度O()

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

折半插入排序

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

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

插入到LOW的位置

性能分析

空间复杂度O(1)

时间复杂度O()

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

希尔排序

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

将原序列划分为一系列形如{i,i+d,i+2d,...,i+kd}的子序列

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

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

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

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

实现

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

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

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

a[j+d]=temp;

性能分析

空间复杂度O(1)

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

稳定性：不稳定

只适用于顺序表

交换排序

冒泡排序

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

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

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

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

性能分析

空间复杂度O(1)

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

每次交换要移动3次元素

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

稳定性：稳定

可用于链表

快速排序

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

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

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

QuickSort(a,b)

if a-b=1 return;

ElemType* low=0, high=n-1;
pivot=*low;

while low≠high

while *high≥pivot

high--;

*low=*high;

while *low<pivot

low++；

*high=*low；

*low=pivot;

QuickSort(0,low-1);
QuickSort(low+1,n-1);

性能分析

空间复杂度O()

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

有序、逆序效率最差

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

稳定性：不稳定

例：221

选择排序

简单选择排序

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

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

性能分析

空间复杂度O(1)

时间复杂度O()

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

稳定性：不稳定

可用于链表

堆排序(heap)

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

Struct 堆：
0号结点空

结构

大根堆：

小根堆：

二叉树的顺序存储

i的左孩子

i的右孩子

2i+1

i的父结点

floor(i/2)

i所在层

或

是否有xx

编号≤n

是否是叶子

方法

筛选法建堆

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

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

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

Adjust(a[i])

循环形式

=;//另存结点值
//筛选子结点
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;

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

插入元素

//新元素不断上升，直到无法继续
while (isInverse(this, this / 2) || this == 1){
swap(this, this / 2); this /= 2;}

O()

删除元素

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

O()

实现

HeapSort(a)

BuildHeap(a);

for len from len to 1

Swap(a[1],a[len]);