08 2024考研408-数据结构 第八章-排序学习笔记

一、排序的基本概念

旧金山大学的数据结构与算法在线动效：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

---

1.1、认识排序

---

1.2、排序算法的应用

---

1.3、排序算法的指标

①时间、空间复杂度。

②稳定性：若是原本相同的两个数字一个前一个后在进行排序之后，两个数字发生了对调，此时可以说明其是不稳定的，若是没有发生对调则表示其是稳定的。

---

1.4、排序算法的分类（内部、外部）

对于外部排序，若是数据太多则需要一批一批去读取到内存中来进行排序。

---

二、 插入类排序

2.1、插入排序

2.1.1、认识插入排序

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

核心代码案例举例：

①插入76

例如当指针移动到76的时候，我们需要依次和之前的数字进行比较，若是一旦有个数字是>76，则进需要进行移动：

最终就插入到如下图位置：

②插入27

---

2.1.2、算法代码实现（朴素代码及带哨兵代码实现）

朴素代码实现：

带哨兵的代码实现：数组多出一个位置来存储哨兵，之后将每次比较的元素放到哨兵位置来进行比较，可以省去一个比较条件

---

2.1.3、算法效率比较

最好情况：O(n)

最坏情况：O(n²)

---

2.1.4、优化：折半插入排序

思路：针对于当前元素找到之前排序数序列中要插入的位置原本是从后往前，现在则可以在之前序列中使用二分查找。

由于中间过程移动元素的次数没有改变，所以时间复杂度依旧是O(n²)。

---

扩展：可对链表使用插入排序

时间复杂度依然为O(n²)，在链表中我们无法来进行使用二分，但是在对于移动元 素的次数变少，但是关键字对比数量依旧为O(n²)：

---

知识点回顾与重要总结

---

2.2、希尔排序（基于插入排序）

2.2.1、认识希尔排序

叫做希尔的发明的，是插入排序的优化。

---

2.2.2、希尔排序的流程

我们对下方来进行希尔排序：

根据每趟d产生的子表，我们来对其进行排序：

接着第三趟，此时当前的序列已经达成了一个基本有序的情况：

最后进行一次直接插入，即可完成排序：

注意：在考研中常常会自己去定义增量d的大小，有可能是3。

---

2.2.3、算法代码实现

---

2.2.4、算法性能分析（稳定性及时间空间复杂度）

时间/空间复杂度

在最坏情况下，d=1时，则可能出现最坏时间复杂度O(n²)

稳定性

注意：希尔排序实现只能基于顺序表，不适用于链表！

---

知识点回顾与重要总结

---

三、交换类排序

3.1、冒泡排序

3.1.1、认识冒泡排序

每一趟可以找对应区间中最小的那个值放到最前面：

若是在一趟过程中没有出现交换的情况，那么表示当前序列已经是有序的了。

---

3.1.2、冒泡排序的流程

第一趟的过程就是从后往前依次进行比较，将小的元素进行往前交换，直到整个序列中最小的元素移动到第一个位置：

之后的每一趟都是这个思路，不断的将最小的值向前冒泡：

---

3.1.3、算法代码实现

其中的flag就是表示当一趟过程比较大小中没有出现交换情况，那么表已经有序即可以退出：

---

3.1.4、算法性能分析（稳定性、时间与空间复杂度）

稳定性：冒泡排序算法是稳定的！

时间与空间复杂度：

在对应的排序过程中，考研试题会去比较移动元素或者交换次数，一定要会懂得区分！！！

注意：对于链表可以从前往后依次进行对比，将更大的元素往后移动进行交换，最终最大的元素就会往后冒。

• 之前非链表是可以从前往后按照大元素往后冒，从后往前小元素往前冒。

---

知识点回顾与总结

---

3.2、快速排序

3.2.1、认识快速排序

每一次都会使一个中间元素确定它的最终位置

---

3.2.2、快速排序的流程

首先选择一个枢纽（可选择开头的一个或者随机），定义一个low以及high指针方便之后来进行填入数据：

由于我们的枢纽是49，那么对于左右两边我们要分别找到左边<=49，以及右边>=49的所有值：

首先从high开始，49<=枢纽值，那么high直接左移，接着当前high指向的27是<=49，此时我们需要将49移动到low指向的位置：

接着low向右移动，此时38<=49符合，继续low向右移动到位置2，此时65>49，此时则需要将65移动到high的位置：

此时low++，接着从high位置开始继续向前找到<49的数，此时定位到位置5，接着将13移动到low位置，low++：

此时low指向的位置为97，其>49，那么就需要将97移动到high位置，low++：

接着从high开始继续向前，由于在low及之后目前都是>=49了，此时这一轮的paration分区完成！

此时我们就分为左右两个小分区，使用递归来进行依次对分区处理：

之后左右两边分区分别是[0, 2]、[4, 7]，进行两轮paration，之后同样如此进行反复最终就能完成整个序列有序！

---

3.2.3、算法代码实现

---

3.2.4、算法效率分析

3.2.4.1、关于层数及递归深度说明

关于QuickSort的层数：

对于快速排序的深度，我们可以根据二叉树的高度来进行计算

---

3.2.4.2、最好与最快情况案例说明

最好的情况

若是每一次选中的枢轴将待排序的序列分为均匀的两个部分，则递归深度最小，算法效率最高。

举例如下：

最坏的情况

1、若是每一次选中的枢轴将待排序的序列分为很不均匀的两个部分，则递归深度最小，算法效率最高。

2、若是初始序列有序或者逆序，则快速排序的性能最差（因为每次都是选择最靠边的元素）

举例如下：初始即为排序，那么高度即为n层效率最低

---

3.2.5、总结时间空间效率分析及稳定度

稳定性：不稳定

不稳定的举例如下：

以0号为竖轴，high位置值<2，所以1放置到0号位置，接着low++：

接着low指针当前的2是<=2，那么low继续右移，此时low==high，原本的2就会填入到对应的位置，此时原始的相同元素位置发生了改变，说明其就是不稳定的！

---

3.2.6、快速排序优化思路

---

3.2.7、知识点回顾与总结

---

PS：关于408中对于一趟与一次划分的定义解读

408考题中对于一趟的定义可以说找到多个枢轴的中心位置：

而对于一次的划分只是针对于一个区间调用一次pariation：

---

四、选择类排序

4.1、简单选择排序

4.1.1、认识简单选择排序

---

4.1.2、简单选择排序的流程

首先找到全部序列中从左到右，最小的元素13并将其与之前进行交换。

第一趟找到最小元素13，将其移动到第一个位置。

第二趟找到位置在[1, 7]中最小的元素27，并进行移动到第二个位置：

第三趟找到位置在[2, 7]中最小的元素38，并进行移动到第三个位置：

第四趟找到位置在[3, 7]中最小的元素49（第一个出现的），并进行移动到第四个位置：

第五趟找到位置在[4, 7]中最小的元素49，并进行移动到第五个位置：

第6趟如下：

第7趟如下：

最后一趟无需处理因为只有1个，所以总共进行了n-1趟排序！

---

4.1.3、算法代码实现

---

4.1.4、算法性能分析

算法稳定性：不稳定

---

知识点回顾与重要总结

注意：中间过程中比较趟数有n-1趟。

---

4.2、堆排序

4.2.1、认识堆排序

与之前选择排序的思想一致：每一趟在待排序元素中选取关键字最小(或最大)的元素加入到有序子序列中。

包含有大根堆，小根堆：

可以注意到这里的2i与2i+1实际上就对应了之前二叉树使用数组存储时一个节点的左孩子与右孩子，如下：

什么是堆？

• “堆”应当将其看成是顺序存储的二叉树。

对于大顶堆，其中根>=左、右，具体图见如下：

小顶堆：与大顶堆相同，对应的根节点<=左、右

---

4.2.2、如何基于“堆”进行排序？

若是将一个原始数组整理成堆，此时从堆来看，若是堆顶的关键值是最大的，那么就很容易来使用选择排序。

步骤一：建立大根堆

给定一个原始序列，来构建大根堆，也就是根>=左、右的形态。

由于非终端节点的编号i <= [n/2]，即我们需要去遍历前四个节点(总8个节点)即可查询所有节点，从后往前依次进行。

思路：将前四个(非终端节点)检查一遍，看是否满足大根堆要求，若是不满足则进行调整！

①首先从前四个元素中的最后一个开始，也就是数9，首先来检查以9位根的部分是否满足大顶堆的要求：

• 可以根据2i、2i+1来找到对应根节点的左孩子与右孩子。

检查09的左右孩子可以发现32>9，此时我们将9与32进行互换，此时就构成了大根堆：

②接下来我们继续向前进行处理，处理数值78

同样对以78为根的子树，检查左右孩子是否有>78的，若是有，则进行交换最大的一个，此时可以检测到右孩子87>78，此时将其进行交换：

③接着继续向前进行处理17：

通过检查发现右孩子最大，则17与45进行交换，此时同样以45为根节点即符合“大根堆”：

④接着继续向前处理53，由于右孩子更大，则跟右孩子进行互换

互换之后，可以看到当前这棵树已经构成了大根堆：

---

步骤二：基于大根堆进行排序（大顶堆构成增序序列）

思路：基于选择排序的思想，每一趟将堆顶元素加入到有序子序列（将最大的堆顶元素与最后一个位置进行交换，接着去调整剩余n-1个为大顶堆）。

第一趟：将堆顶最大值与最后一个位置进行交换，并进行下坠节点构成大顶堆

①将堆顶最大值与最后一个位置进行交换

此时堆顶元素是最大值，那么我们将最大的堆顶元素与最后一个位置值进行交换，此时就将最大值找到并添加到最后

此时87这个数值位置就无需再改变了！

接下来我们将除了87的看做是一个堆来继续进行：

注意此时上面画圈的已经不是一个大根堆，此时我们则需要对09这个值来进行下坠调整：

②进行下坠节点构成大顶堆，将09元素值进行不断下坠

首先其右孩子是最大的，则跟其进行互换：

此时还没有下坠到最后一层，又当前左孩子是最大的，来进行交换，此时09下坠调整已经结束：

此时当前除了87的堆已经再次构成大根堆：

OK，此时完成了第一趟处理操作！！！

步骤二：进行第二趟的处理，将堆顶元素与堆底元素进行互换，接着再次构建大顶堆

此时完成交换，此时大顶堆中最大的元素再此放置到了最后一个位置：

此时78、87已经完成了排序，不再参与到之后的大跟堆排序当中！

接着我们对53为根节点的堆来进行调整为大顶堆：

首先53与65进行互换：

接着由于只有一个左孩子参与到大顶堆调整中，而9<53所以无需进行互换！

步骤三：接着进行第三趟，与之前同样大顶堆堆顶与堆底元素进行互换

此时根据下面堆来进行调整为大顶堆，将09元素不断下坠：

步骤四：第四趟，同理将堆顶最大元素与堆底元素进行互换

此时将17来进行下坠：

步骤五：第五趟，将45与17进行互换，同样17进行下坠

此时将17进行下坠：

步骤六：第六趟，将32与09进行互换，同样09进行下坠

接着将09进行下坠：

步骤七：第七趟，由于是最后一个序列，则需要进行交换，此时就构成了最大排序！

结论：根据“大顶堆”排序可以得到增序序列。

---

4.2.3、算法代码实现

①建立大根堆代码（含过程演示）

实现代码

从len/2及之前开始进行调整大根堆。

演示最后一个节点53情况

直接跳过后面三个节点，直接快进到最后一趟：

此时确定右孩子更大，接着我们去判断当前53是否>=最大节点，若是已经最大，那么表示无需进行调整，若是不是最大，则需要将最大的节点放置到当前的k位置上，并且调整当前指针指向下方的一个比其小的节点。

接着我们继续将交换过后的节点(指向53的索引)与下面左右孩子进行对比：

最终将78插入到53这个位置完成小元素的下坠：

此时最初始的大根堆就建立完成了。

---

②基于大根堆排序代码

---

4.2.4、算法性能分析

关于堆下坠调整函数及初始构建大根堆的时间复杂度分析

堆下坠调整函数案例介绍

假设当前从09开始进行对比：

则总共需要去比较两次，第一次是09与96、32比较需要比较两次，第二次则是与左孩子42进行比较，需要比较1次。

初始建大顶堆具体分析

关于上图红色框的式子计算：将h代入到对应式子，即可以得到为2n*【j/2^j，j∈[1, h - 1]】

注意这个j/2^j，j∈[1, h - 1]，计算如下：

最终可以确定建立大根堆的时间复杂度为O(n)，调整为大跟堆的时间复杂度为O(logn)。

---

关于堆排序的时间复杂度分析

由于总共需要n-1趟，每交换一趟后就需要进行下坠调整，此时对于堆排序的时间复杂度为O(n.logn)。

---

总结分析

稳定性：不稳定

稳定性举例

首先需要初始大根堆，首先去进行1进行下坠：

优先与左孩子进行交换：

接着进行堆排序：

首先将堆顶元素与最后一个堆元素进行互换：

接着堆顶元素与最后一个元素进行互换：

此时排序到此结束！可以看到与原先相等序列情况不一致，说明该排序是不稳定的：

---

知识点回顾与总结

---

4.2.5、堆排序的插入与删除

插入

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

详细过程：

案例1：插入数13

我们在小根堆中插入一个数13，首先会将其放入到表尾：

插入到末尾之后此时已经破坏了小根堆，此时就需要将13不断的进行上升与父节点进行比较，此时13<32，那么就需要进行交换：

此时又13<17，再次进行互换：

此时13>9，此时则不再进行交换，整个过程进行了3次比较！

案例2：插入46

此时46与父节点进行比较，由于46>45不进行交换，此时上升比较就结束了！总共比较次数为1次！

---

删除

思路：删除指定位置的元素，然后将堆底的元素填补上去，接着来让该节点不断进行下坠

详细过程：

假设要删除13，此时13位置删除，接着将堆中末尾元素移动到该删除的位置：

此时我们需要做的事情就是不断的让元素46进行下坠，由于17<46，进行交换：

此时还需要与46下面的两个孩子进行对比，将更小的孩子换上来：

此时已经到了末尾，我们无法再进行调整，结束。

整个对比关键字的次数为4次。

---

知识点回顾与总结

---

五、归并排序与基数排序

5.1、归并排序

5.1.1、认识归并排序

什么是归并？将两个或多个已经有序的序列合并成一个。

举例：给出两个连续的序列，接着依次从第一个位置开始比较，优先将小的数放入的下方的序列中，最终合并称为一个有序序列！

最终效果：

2路归并：将两个有序序列合二为一。

多路归并：多个有序序列合并为一，例如4路(四合一)归并。

• 对于4路，每选出来1个就需要对比3次。

---

5.1.2、归并排序的实现流程

归并排序通常是使用2路归并排序的。

下面是归并排序的实现流程，从最小的1个部分开始，接着不断的进行归并，最终合并为一个有序序列：

---

5.1.3、算法代码实现

Merge合并代码

①先进行拷贝一份到B数组

②接着在B数组中依次比较i与j，最终合并为有序序列放置到A数组中

完整代码如下

可以看到Merge到最下面就是上面的实现流程的初始序列状态，1个1个，接着之后来进行合并：

---

5.1.4、算法性能分析

归并排序的时间复杂度实际上为：趟数*每趟比较的次数

对于趟数：我们实际上可以将归并排序的归并过程看作是一课树，趟数实际上就是这棵树的高度O(logn)。

每趟比较的次数：实际上我们合并的组数虽然在减少，但是组中间的数也是在变多，实际上每一趟过程中比较的次数时间复杂度为O(n)

• 实际上还要加上递归的趟数O(logn)，但是O(n)>O(logn)，所以这里可以保留更高阶的空间复杂度O(n)。

无论给出的序列是有序还是无序，最终的时间复杂度为O(n.logn)【最好最坏时间复杂度】。

关于稳定性：稳定。

• 我们在合并过程中，可以去自己手动的编写代码来控制左边的还是右边先加入到有序序列当中。
• 

---

知识点回顾与总结