王道数据结构第八章排序_思维导图模板

第八章排序

排序的基本概念

排序，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程

评价指标

算法的稳定性，关键字相同的两个元素，在排序前后的相对位置不变，则称这个排序算法是稳定的，否则是不稳定的

时间、空间复杂度

排序算法

内部排序

关注如何使算法的时间复杂度和空间复杂度更低

外部排序

还要关注如何使读/写磁盘次数更少

内部排序

插入排序

算法思想

每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成

代码实现

性能分析

空间复杂度：O(1)

时间复杂度

最好时间复杂度：O(n)

最坏时间复杂度：O(n²)

平均时间复杂度：O(n²)

算法稳定性：稳定

优化

折半插入排序

折半查找找到应插入的位置，仅适用于顺序表

注意：一直到low>high时才停止折半查找。当mid所指元素等于当前元素时，应继续令low=mid+1，以保证“稳定性”。最终应将当前元素插入到low所指位置（即high+1）

比起直接插入排序，只减少了比较关键字的次数，时间复杂度仍是O(n²)

希尔排序

算法思想

先追求表中元素部分有序，再逐渐逼近全局有序

先将待排序表分割成若干形如L[i,i+d,i+2d,...,i+kd]的“特殊”子表，对各个子表分别进行直接插入排序。缩小增量d，重复上述过程，直到d=1为止。

代码实现

性能分析

空间复杂度：O(1)

时间复杂度：和增量序列的选择有关，目前无法用数学手段证明确切的时间复杂度，但优于插入排序

算法的稳定性：不稳定

适用性：仅可用于顺序表

交换排序

冒泡排序

算法思想

从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A[i]），则交换它们，直到序列比较完。称这样过程为“一趟”冒泡排序。最多只需n-1趟排序

每一趟排序都可以使一个元素移动到最终位置，已经确定最终位置的元素在之后的处理中无需再次对比

如果某一趟排序过程中未发生“交换”，则算法可以提前结束

每次交换都要移动元素三次

代码实现

性能分析

空间复杂度：O(1)

时间复杂度

最好时间复杂度：O(n)

最坏时间复杂度：O(n²)

平均时间复杂度：O(n²)

算法稳定性：稳定

适用性：顺序表，链表都可以

快速排序

算法思想

在待排序表L[1...n]中任取一个元素pivot作为枢轴（或基准，通常取首元素），通过一趟排序将待排序表划分为独立的两部分L[1...k-1]和L[k+1...n]，使得L[1...k-1]中的所有元素小于pivot，L[k+1...n]中的所有元素大于等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为一次“划分”。然后分别递归地对两个子表重复上述过程，直至每部分只有一个元素或空为止，即所有元素放在了其最终位置上。

算法表现主要取决于递归深度，若每次“划分”越均匀，则递归深度越低。
“划分”递归深度越深。

代码实现

性能分析

空间复杂度

最好：O(n)

最坏：O(log n)

时间复杂度

最好：O(n²)

最坏：O(n log n)

平均：O(n log n)

稳定性：不稳定

408原题：一次划分≠一次排序

选择排序

简单选择排序

算法思想

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

n个元素进行n-1次处理

代码实现

性能分析

空间复杂度：O(1)

时间复杂度：O(n²)

稳定性：不稳定

适用性：顺序表，链表都可以

堆排序

算法思想

顺序存储的“完全二叉树”

堆：若n个关键字序列L[1...n]满足下面某一条性质，则称为堆

1.若满足：L(i)≥L(2i)且L(i)≥L(2i+1) (1≤i≤n/2)——大根堆

2.若满足：L(i)≤L(2i)且L(i)≤L(2i+1) (1≤i≤n/2)——小根堆

可以理解成一棵完全二叉树
大根堆：根≥左，右
小根堆：根≤左，右

把所有的非终端结点都检查一遍，是否满足大根堆的要求，如果不满足，则进行调整

在顺序存储的完全二叉树中，非终端结点编号i≤[n/2]

检查当前结点是否满足根≥左，右，若不满足，将当前结点与更大的一个孩子互换（自底向上处理各分支结点）

i的左孩子——2i

i的右孩子——2i+1

i的父节点——[i/2]

若元素互换破坏了下一级的堆，则采用相同的方法继续往下调整（小元素不断“下坠”）

堆排序：每一趟将堆顶元素加入有序子序列（与待排序序列中的最后一个元素交换），并将待排序元素序列再次调整为大根堆（小元素不断“下坠”）

基于大根堆的堆排序得到“递增序列”，基于小根堆的堆排序得到“递减序列”

代码实现

性能分析

空间复杂度：O(1)

时间复杂度

建堆的时候，关键字对比次数不超过4n，建堆时间复杂度=O(n)

堆排序的时间复杂度：O(n log n)

稳定性：不稳定

堆的插入删除

插入

对于小根堆，新元素放到表尾，与父节点对比，若新元素比父节点更小，则将二者互换。新元素就这样一路“上升”，直到无法继续上升为止

删除

被删除的元素用堆底元素替代，然后让该元素不断“下坠”，直到无法下坠为止

归并排序

算法思想

把两个或多个已经有序的序列合并成一个

2路归并的“归并树”——形态上就是一棵倒立的二叉树

n个元素进行2路归并排序，归并趟数=[log n]

实现步骤

若low

对左半部分[low,mid]递归地进行归并排序

对右半部分[mid+1,high]递归的进行归并排序

将左右两个有序子序列Merge为一个

代码实现

性能分析

空间复杂度：O(n)

时间复杂度

每趟归并的时间复杂度：O(n)

算法的时间复杂度：O(n log n)

稳定性：稳定

基数排序

算法思想

过程

第一趟分配：以“个位”进行“分配”

第一趟收集结束：得到按个位“递减”排序的序列

第二趟分配：以“十位”进行“分配”

第二趟收集结束：得到按“十位”递减排序的序列，十位相同的按个位递减排序

第二趟分配：以“百位”进行“分配”

第三趟收集结束：得到按“百位”递减排序的序列，百位相同的按十位递减排序，十位相同的按个位递减排序

假设长度为n的线性表中每个结点的关键字由d元组(,,,...,,)组成，其中0≤≤r-1(o≤k＜n,0≤i≤d-1)，r称为“基数”

基数排序得到递减序列的过程如下

初始化：设置r个空队列，,,...,

按照各个关键字位权重递增的次序（个，十，百），对d个关键字位分别做“分配”和收集

分配：顺序扫描各个元素，若当前处理的关键字位=x，则将元素插入队尾，一趟分配耗时O(n)

收集：把,,...,各个队列中的结点依次出队并链接，一趟收集耗时O(r)

代码实现

性能分析

空间复杂度：O(r)

时间复杂度：O(d(n+r))

稳定性：稳定

适用性：善于处理

1.数据元素的关键字可以方便地拆分为d组，且d较小

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

3.数据元素个数n较大

外部排序

外存与内存之间的数据交换

操作系统以“块”为单位对磁盘存储空间进行管理，如每块大小1KB，每个磁盘块内存放着各种而样的数据

磁盘的读/写以“块”为单位，数据读入内存后才能被修改，修改完了还要写回磁盘

外部排序

外部排序的原理

外部排序：数据元素太多，无法一次全部读入内存进行排序

若要进行k路归并排序，则需要在内存中分配k个输入缓冲区和1个输出缓冲区

步骤

生成r个初始归并段（对L个记录进行内部排序，组成一个有序的初始归并段）

进行S趟k路归并，S=[]

k越大，r越小，归并趟数越少，读写磁盘次数越少

如何进行k路归并

把k个归并段的块读入k个输入缓冲区

用“归并排序”的方法从k个归并段中选出几个最小记录暂存到输出缓冲区中

每当一个输入缓冲区为空时，立即输入下一块待排数据

当输出缓冲区满时，写出外存

外部排序时间开销

读写外存的时间

内部排序所需时间

内部归并所需时间

优化思路

多路归并

需要增加相应的输入缓冲区

每次从k个归并段中选一个最小元素需要（k-1）次关键字对比

采用多路归并可以减少归并趟数，从而减少磁盘I/O（读写）次数

减少初始归并段数量

若能增加初始归并段长度，则可减少初始归并段数量r

按照本节课介绍的方法生成的初始归并段，若共有N个记录，内存工作区可以容纳L个记录，则初始归并段数量r=N/L

纠错：k路平衡归并

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

2.每一趟归并中，若有m个归并段参与归并，则经过这一趟处理得到[m/k]个新的归并段

败者树

使用k路平衡归并策略，选出一个最小元素需要对比关键字（k-1）次，导致内部归并所需时间增加————————————可以用败者树解决！

什么是败者树

败者树——可视为一棵完全二叉树（多了一个头）。k个叶结点分别是当前参加比较的元素，非叶子结点用来记忆左右子树中的“失败者”，而让胜者往上继续进行比较，一直到根结点

原理

每个叶子结点对应一个归并段

分支结点记录失败败者来自哪个归并段

根节点记录冠军来自哪个归并段

性能分析

对于k路归并，第一次构造败者树需要对比关键字k-1次

有了败者树，选出最小元素，只需对比关键字[]次

置换-选择排序

若共有N个记录，内存工作区可以容纳L个记录，则初始归并段数量r=N/L———可用“置换-选择排序”进一步减少初始归并数量

设初始待排文件为FI，初始归并段输出文件为FO，内存工作区为WA，FO和WA的初始状态为空，WA可容纳w个记录。置换-选择算法的步骤如下

1.从FI输入w个记录到工作区WA

2.从WA中选出其中关键字取最小值的记录，记为MINIMAX记录

3.将MINIMAX记录输出到FO去

4.若FI不空，则从FI输入下一个记录到WA中

5.从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录

6.重复3-5，直至在WA中选不出新的MINIMAX记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到FO中去

7.重复2-6，直至WA为空，由此得到全部初始归并段

最佳归并树

归并块的神秘性质

归并过程中的磁盘I/O次数=归并树的WPL*2

要让磁盘I/O次数最小，就要使归并树WPL最小——哈夫曼树

对于k叉归并，若初始归并段的数量无法构成严格的k叉排序树，则需要补充几个长度为0的“虚段”，再进行k叉哈夫曼树的构造

如何构造

补充虚段

1.若（初始归并段数量-1）%（k-1）=0，说明刚好可以构成严格k叉树，此时不需要添加虚段

2.若（初始归并段数量-1）%（k-1）=u≠0，则需要补充（k-1）-u个虚段

构造k叉哈夫曼树

每次选择k个根结点权值最小的树合并，并将k个根节点的权值之和作为新的根节点的权值

王道数据结构第八章排序

模板简介

猜你喜欢

相关文章

王道数据结构 第八章 排序

模板简介

猜你喜欢

相关文章

王道数据结构第八章排序