Lecture 9 排序算法 | JAY’s Blog

概述插入排序直接插入排序算法流程算法特性折半插入排序 / 二分法插入排序希尔排序/缩小增量排序(Shell Sort)交换排序冒泡排序快速排序(分划交换排序)基本思想算法性质代码实现选择排序直接选择排序锦标赛排序(树形选择排序)算法思想算法性质算法实现堆排序算法思想算法流程算法性质算法实现归并排序递归的归并排序算法流程算法性质算法实现迭代的归并排序递归的链表归并排序基数排序

概述

排序：n个对象的序列R[0],R[1],R[2],…R[n-1] 按其关键码的大小，进行由小到大（非递减）或由大到小（非递增）的次序重新排序的。

关键码（key）→ 即键值

两大类：

内排序：对内存中的n个对象进行排序(插入排序，交换排序，选择排序，归并排序，基数排序)
外排序：内存放不下，还要使用外存的排序。

稳定性: 如果待排序的对象序列中，含有多个键值相等的对象，用某种方法排序后，这些对象的相对次序不变的，则是稳定的，否则为不稳定的。

稳定排序是多级排序场景的必要条件。假设我们有一个存储学生信息的表格，第 1 列和第 2 列分别是姓名和年龄。在这种情况下，非稳定排序可能导致输入数据的有序性丧失.

就地性：顾名思义，原地排序通过在原数组上直接操作实现排序，无须借助额外的辅助数组，从而节省内存。通常情况下，原地排序的数据搬运操作较少，运行速度也更快。

自适应性：自适应排序能够利用输入数据已有的顺序信息来减少计算量，达到更优的时间效率。自适应排序算法的最佳时间复杂度通常优于平均时间复杂度。

是否基于比较：基于比较的排序依赖比较运算符（<、=、>）来判断元素的相对顺序，从而排序整个数组，理论最优时间复杂度为。而非比较排序不使用比较运算符，时间复杂度可达，但其通用性相对较差。

排序的算法分析: 时间开销(比较次数, 移动次数), 所需的附加空间. 理想的排序算法运行快、原地、稳定、自适应、通用性好。显然，迄今为止尚未发现兼具以上所有特性的排序算法。因此，在选择排序算法时，需要根据具体的数据特点和问题需求来决定。

平均查找长度ASL(Average Search Length): 查找每个数的平均搜索/比较次数(概率相等取算数平均, 概率不等则加权平均)

插入排序

直接插入排序

扑克牌理牌, 依次将元素插入结果序列中的正确位置

💡

对升序排序, 找到有序序列中最大的小于等于待插入元素的元素, 将待插入元素插入该元素的右侧.

直接插入排序可以边比较边移动, 折半插入排序则只能先找到再移动

算法流程

算法特性

折半插入排序 / 二分法插入排序

改遍历为二分查找 / 折半查找, 定位插入位置

见少了比较次数, 但是元素移动次数不变, 平均时间复杂度为, 空间复杂度, 是稳定的排序算法

💡

折半查找: 必须是数组(顺序表), 必须有序

折半查找的判定树: 以中间节点作为根节点, 左右部分作为左右子树递归构建

应该会得到该序列以中间元素作为根节点的搜索树

元素在第几层, 找到他就需要比较多少次

构建判定树之后就可以很方便的求出平均查找长度(成功时的/失败时的)

查找失败 → 给目前所有的空指针域加上失败节点(外部节点), 代表不存在的数据区间

希尔排序/缩小增量排序(Shell Sort)

简单的插入排序可能存在的问题: 当需要插入的数是较小的数时，数组元素后移的次数明显增多，对效率有影响

希尔排序也是一种 插入排序，它是简单插入排序经过改进后的一个 更高效的版本，也称为 缩小增量排序

希尔排序把记录按 下标的一定增量分组，对每组使用 直接插入排序算法 排序，随着 增量逐渐减少，每组包含的键值越来越多（要排序的数），当增量减至 1 时，整个待排序序列被分成一组，算法终止。

💡

seq[i]和seq[i + n*gap]分到同一组

每一轮增量gap /= 2?

交换排序

方法的本质：不断的交换反序的对偶，直到不再有反序的对偶为止。

两种方法: 冒泡排序 / 快速排序

冒泡排序

基本思想：通过对待排序序列 从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒。

流程:

1）从头到尾做一遍相邻两元素的比较，有颠倒则交换，记下交换的位置。

一趟结束，一个或多个最大（最小）元素定位。

2）去掉已定位的的元素，重复1)，直至一趟比较下来无交换。

优化: 因为排序过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志判断元素是否进行过交换。从而减少不必要的比较。

快速排序(分划交换排序)

基本思想

Quicksort 快速排序 是对 冒泡排序的一种改进。

基本思想: 通过一趟排序将要排序的数据 分割成独立的两个部分，一部分的所有数据都比另外一部分的所有数据都要小。然后再按如上的方法对这两部分数据分别进行快速排序，排序过程可以递归进行，以此达到整个数据变成有序序列。

算法性质

快速排序不稳定, 平均时间复杂度

三数中值分割法（Median-of-Three partitioning) : 对N个数的序列，最好选第个最大数作为pivot，这是最好的中值，但这是很困难的。一般选左端、右端和中心位置上的三个元素的中值作为pivot。

代码实现

选择排序

直接选择排序

选择排序（selection sort）的工作原理非常简单：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。

锦标赛排序(树形选择排序)

算法思想

锦标赛排序（英文：Tournament sort），又被称为树形选择排序，是选择排序的优化版本，堆排序的一种变体（均采用完全二叉树）。它在选择排序的基础上使用优先队列查找下一个该选择的元素。

锦标赛排序的名字来源于单败淘汰制的竞赛形式。在这种赛制中有许多选手参与比赛，他们两两比较，胜者进入下一轮比赛。这种淘汰方式能够决定最好的选手，但是在最后一轮比赛中被淘汰的选手不一定是第二好的——他可能不如先前被淘汰的选手。

一轮建立, 多轮重建

💡

和堆一样都利用树, 但是锦标赛排序的所有待排序元素都在叶节点上, 而堆排序的元素在整个树中

算法性质

算法实现

为什么最小值是tmp[tmp[1]]而不是tmp[1]?
tmp[1] 中存储的是 胜者节点的索引，而 真正的最小值 存储在 tmp[tmp[1]] 中。
💡
tmp数组的前n个元素(下标范围0~n-1)存储的是多级锦标赛的胜者的叶节点下标(范围n~2n-1)
具体原因可以通过锦标赛树的构造过程解释：
1. 锦标赛树的存储结构
tmp 数组的后半部分 (tmp[n] 到 tmp[2n-1]) 存储的是输入数组 a 的实际值（叶子节点）。
tmp 数组的前半部分 (tmp[1] 到 tmp[n-1]) 存储的是每场比较的胜者索引（中间节点）。
tmp[1] 是树根，它存储的是整个锦标赛树的 最终胜者的索引，而不是值。
2. 构造树的逻辑
在构造树时：
每个父节点存储的是两个子节点（或叶子节点）中胜者的索引。
例如：
如果 tmp[2] 和 tmp[3] 进行比较，胜者的索引被存储在 tmp[1] 中。
3. 取最小值的逻辑
树根 tmp[1] 存储了最终胜者的索引。
实际的最小值存储在 tmp[tmp[1]] 中：
tmp[1] 是最小值的索引。
tmp[tmp[1]] 是通过该索引获取的最小值。

将 tmp 数组的前后两半存储不同的对象（索引和数值）主要是为了高效地维护锦标赛树，尤其是在重建树时快速更新父节点的胜者。以下是设计的原因和优劣对比：
原因分析
1. 便于快速更新锦标赛树
锦标赛树需要在删除最小值后重新调整胜者。
如果存储的统一是数值，那么父节点需要通过子节点的值重新找到胜者，并将对应值存储回去，这会引入额外的逻辑来记录胜者的位置。
存储索引则可以通过简单的索引比较 (winner 函数) 快速更新父节点，同时保留胜者的位置。
2. 避免多次复制和传递数据
如果所有节点直接存储值，则在更新过程中，父节点需要逐层传递值和索引。这会引入数据复制的开销。
当前设计通过索引间接访问值，减少了数据传递的复杂性和冗余。
3. 为原数组 a 保持引用
叶子节点直接指向原数组的索引，这样在后续排序过程中，重建树时无需额外拷贝或调整原数组的数据。
通过索引操作即可直接修改数组值。
优劣对比
当前设计（索引+值分离）
优点：
高效更新：重建树时，通过索引快速找到胜者，无需重复计算或传递。
空间节省：tmp 数组只需要存储索引和少量中间值，避免存储多份实际数据。
逻辑统一：对于叶子和中间节点操作一致，都通过索引访问实际值。
缺点：
理解复杂：需要额外维护索引和值的映射关系，增加了初学者的理解难度。
不够直观：从 tmp 读取最小值时，需要间接访问，增加了代码的解读成本。
统一存储数值
优点：
逻辑清晰：所有节点直接存储值，逻辑直观，无需通过索引间接访问。
简化代码：消除索引操作，简化节点比较和更新逻辑。
缺点：
父节点更新复杂：更新树时，需要遍历左右子节点找到胜者及其对应的索引，增加计算开销。
空间冗余：需要在树中多次存储同一个值。

堆排序

算法思想

堆排序（英语：Heapsort）是指利用 二叉堆 这种数据结构所设计的一种排序算法。堆排序的适用数据结构为数组。堆排序的本质是建立在堆上的选择排序。

算法流程

首先建立大顶堆，然后将堆顶的元素取出，作为最大值，与数组尾部的元素交换，残余堆元素个数—, 并维持残余堆的性质；

之后将堆顶的元素取出，作为次大值，与数组倒数第二位元素交换，并维持残余堆的性质；

以此类推，在第次操作后，整个数组就完成了排序。

💡

数组上建立二叉堆的下标系统:

iParent(i) = (i - 1) / 2;
iLeftChild(i) = 2 * i + 1;
iRightChild(i) = 2 * i + 2;

算法性质

算法实现

归并排序

递归的归并排序

算法流程

“划分阶段”从顶至底递归地将数组从中点切分为两个子数组。

计算数组中点 mid ，递归划分左子数组（区间 [left, mid] ）和右子数组（区间 [mid + 1, right] ）。

递归执行步骤 1. ，直至子数组区间长度为 1 时终止。

“合并阶段”从底至顶地将左子数组和右子数组合并为一个有序数组。需要注意的是，从长度为 1 的子数组开始合并，合并阶段中的每个子数组都是有序的。

观察发现，归并排序与二叉树后序遍历的递归顺序是一致的。

后序遍历：先递归左子树，再递归右子树，最后处理根节点。

归并排序：先递归左子数组，再递归右子数组，最后处理合并。

算法性质

归并排序具有稳定性, 合并过程会保留原数组中的先后顺序, 不涉及交换

算法实现

归并排序的实现如以下代码所示。请注意，nums 的待合并区间为 [left, right] ，而 tmp 的对应区间为 [0, right - left] 。

迭代的归并排序

虽然递归的实现方式很简单，通过递归调用就可以实现，但是会占用大量的时间和空间，使得算法的效率下降. 使用迭代的方式代替递归的方式虽然会使得代码的编写变得困难，但是会提高效率。

迭代的过程就是排序实际执行的过程(从递归返回开始), 化成一个个小的排序问题，再合并到一起

递归的链表归并排序

对数组做归并排序的空间复杂度为 O(n)，分别由新开辟数组 O(n) 和递归函数调用 O(logn) 组成，而根据链表特性：

数组额外空间：链表可以通过修改引用来更改节点顺序，无需像数组一样开辟额外空间；

递归额外空间：递归调用函数将带来 O(logn) 的空间复杂度，因此若希望达到 O(1) 空间复杂度，则不能使用递归。

通过递归实现链表归并排序，有以下两个环节：

分割 cut 环节：找到当前链表中点，并从中点将链表断开（以便在下次递归 cut 时，链表片段拥有正确边界）；我们使用 fastslow 快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点。找到中点 slow 后，执行 slow.next = None 将链表切断。递归分割时，输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmp(因为链表是从 slow 切断的)。 cut 递归终止条件：当 head.next == None 时，说明只有一个节点了，直接返回此节点。

合并 merge 环节：将两个排序链表合并，转化为一个排序链表。双指针法合并，建立辅助 ListNode h 作为头部。设置两指针 left, right 分别指向两链表头部，比较两指针处节点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表。返回辅助ListNode h 作为头部的下个节点 h.next。时间复杂度 O(l + r)，l, r 分别代表两个链表长度。当题目输入的 head == None 时，直接返回 None。