Zxy's Blog

归并排序 归并排序（merge sort）是一种基于分治策略的排序算法，包含下图所示的“划分”和“合并”阶段。 划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题。 合并阶段：当子数组长度为 1 时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束。 算法流程 如下图所示，“划分阶段”从顶至底递归地将数组从中点切分为两个子数组。 计算数组中点 mid ，递归划分左子数组（区间 [left, mid] ）和右子数组（区间 [mid + 1, right] ）。 递归执行步骤 1. ，直至子数组区间长度为 1 时终止。 “合并阶段”从底至顶地将左子数组和右子数组合并为一个有序数组。需要注意的是，从长度为 1 的子数组开始合并，合并阶段中的每个子数组都是有序的。 tab 1tab 2tab 3tab 4tab 5tab 6tab 7tab 8tab 9tab...

快速排序 快速排序（quick sort）是一种基于分治策略的排序算法，运行高效，应用广泛。 快速排序的核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。具体来说，哨兵划分的流程如下图所示。 选取数组最左端元素作为基准数，初始化两个指针 i 和 j 分别指向数组的两端。 设置一个循环，在每轮中使用 i（j）分别寻找第一个比基准数大（小）的元素，然后交换这两个元素。 循环执行步骤 2. ，直到 i 和 j 相遇时停止，最后将基准数交换至两个子数组的分界线。 哨兵划分步骤 tab 1tab 2tab 3tab 4tab 5tab 6tab 7tab 8tab 9 哨兵划分完成后，原数组被划分成三部分：左子数组、基准数、右子数组，且满足“左子数组任意元素 ≤\leq≤ 基准数 ≤\leq≤ 右子数组任意元素”。因此，我们接下来只需对这两个子数组进行排序。 “快速排序的分治策略”——哨兵划分的实质是将一个较长数组的排序问题简化为两个较短数组的排序问题。 1234567891011121314def...

插入排序 插入排序（insertion sort）是一种简单的排序算法，它的工作原理与手动整理一副牌的过程非常相似。 具体来说，我们在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。 下图展示了数组插入元素的操作流程。设基准元素为 base ，我们需要将从目标索引到 base 之间的所有元素向右移动一位，然后将 base 赋值给目标索引。 算法流程 插入排序的整体流程如下图所示。 初始状态下，数组的第 1 个元素已完成排序。 选取数组的第 2 个元素作为 base ，将其插入到正确位置后，数组的前 2 个元素已排序。 选取第 3 个元素作为 base ，将其插入到正确位置后，数组的前 3 个元素已排序。 以此类推，在最后一轮中，选取最后一个元素作为 base ，将其插入到正确位置后，所有元素均已排序。 示例代码如下： 1234567891011def insertion_sort(nums: list[int]): """插入排序""" #...

冒泡排序 冒泡排序（bubble sort）通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样，因此得名冒泡排序。 如下图所示，冒泡过程可以利用元素交换操作来模拟：从数组最左端开始向右遍历，依次比较相邻元素大小，如果“左元素 > 右元素”就交换二者。遍历完成后，最大的元素会被移动到数组的最右端。 tab 1tab 2tab 3tab 4tab 5tab 6tab 7 算法流程 设数组的长度为 nnn ，冒泡排序的步骤如下图所示。 首先，对 nnn 个元素执行“冒泡”，将数组的最大元素交换至正确位置。 接下来，对剩余 n−1n - 1n−1 个元素执行“冒泡”，将第二大元素交换至正确位置。 以此类推，经过 n−1n - 1n−1 轮“冒泡”后，前 n−1n - 1n−1 大的元素都被交换至正确位置。 仅剩的一个元素必定是最小元素，无须排序，因此数组排序完成。 示例代码如下： 12345678910def bubble_sort(nums: list[int]): ...

选择排序 选择排序（selection sort）的工作原理非常简单：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。 设数组的长度为 nnn ，选择排序的算法流程如下图所示。 初始状态下，所有元素未排序，即未排序（索引）区间为 [0,n−1][0, n-1][0,n−1] 。 选取区间 [0,n−1][0, n-1][0,n−1] 中的最小元素，将其与索引 000 处的元素交换。完成后，数组前 1 个元素已排序。 选取区间 [1,n−1][1, n-1][1,n−1] 中的最小元素，将其与索引 111 处的元素交换。完成后，数组前 2 个元素已排序。 以此类推。经过 n−1n - 1n−1 轮选择与交换后，数组前 n−1n - 1n−1 个元素已排序。 仅剩的一个元素必定是最大元素，无须排序，因此数组排序完成。 选择排序步骤 tab 1tab 2tab 3tab 4tab 5tab 6tab 7tab 8tab 9tab 10tab 11 在代码中，我们用 kkk 来记录未排序区间内的最小元素： 123456789101112def...

排序算法 排序算法（sorting algorithm）用于对一组数据按照特定顺序进行排列。排序算法有着广泛的应用，因为有序数据通常能够被更高效地查找、分析和处理。 如下图所示，排序算法中的数据类型可以是整数、浮点数、字符或字符串等。排序的判断规则可根据需求设定，如数字大小、字符 ASCII 码顺序或自定义规则。 评价维度 运行效率：我们期望排序算法的时间复杂度尽量低，且总体操作数量较少（时间复杂度中的常数项变小）。对于大数据量的情况，运行效率显得尤为重要。 就地性：顾名思义，原地排序通过在原数组上直接操作实现排序，无须借助额外的辅助数组，从而节省内存。通常情况下，原地排序的数据搬运操作较少，运行速度也更快。 稳定性：稳定排序在完成排序后，相等元素在数组中的相对顺序不发生改变。 稳定排序是多级排序场景的必要条件。假设我们有一个存储学生信息的表格，第 1 列和第 2 列分别是姓名和年龄。在这种情况下，非稳定排序可能导致输入数据的有序性丧失： 12345678910111213141516# 输入数据是按照姓名排序好的# (name, age) ('A',...

小结 二分查找依赖数据的有序性，通过循环逐步缩减一半搜索区间来进行查找。它要求输入数据有序，且仅适用于数组或基于数组实现的数据结构。 暴力搜索通过遍历数据结构来定位数据。线性搜索适用于数组和链表，广度优先搜索和深度优先搜索适用于图和树。此类算法通用性好，无须对数据进行预处理，但时间复杂度 O(n)O(n)O(n) 较高。 哈希查找、树查找和二分查找属于高效搜索方法，可在特定数据结构中快速定位目标元素。此类算法效率高，时间复杂度可达 O(log⁡n)O(\log n)O(logn) 甚至 O(1)O(1)O(1) ，但通常需要借助额外数据结构。 实际中，我们需要对数据体量、搜索性能要求、数据查询和更新频率等因素进行具体分析，从而选择合适的搜索方法。 线性搜索适用于小型或频繁更新的数据；二分查找适用于大型、排序的数据；哈希查找适用于对查询效率要求较高且无须范围查询的数据；树查找适用于需要维护顺序和支持范围查询的大型动态数据。 用哈希查找替换线性查找是一种常用的优化运行时间的策略，可将时间复杂度从 O(n)O(n)O(n) 降至 O(1)O(1)O(1) 。

重识搜索算法 搜索算法（searching...

哈希优化策略 在算法题中，我们常通过将线性查找替换为哈希查找来降低算法的时间复杂度。我们借助一个算法题来加深理解。 给定一个整数数组 nums 和一个目标元素 target ，请在数组中搜索“和”为 target 的两个元素，并返回它们的数组索引。返回任意一个解即可。 线性查找：以时间换空间 考虑直接遍历所有可能的组合。如下图所示，我们开启一个两层循环，在每轮中判断两个整数的和是否为 target ，若是，则返回它们的索引。 代码如下所示： 12345678def two_sum_brute_force(nums: list[int], target: int) -> list[int]: """方法一：暴力枚举""" # 两层循环，时间复杂度为 O(n^2) for i in range(len(nums) - 1): for j in range(i + 1, len(nums)): if nums[i] + nums[j] == target: ...

二分查找边界 查找左边界 给定一个长度为 nnn 的有序数组 nums ，其中可能包含重复元素。请返回数组中最左一个元素 target 的索引。若数组中不包含该元素，则返回 −1-1−1 。 回忆二分查找插入点的方法，搜索完成后 iii 指向最左一个 target ，因此查找插入点本质上是在查找最左一个 target 的索引。 考虑通过查找插入点的函数实现查找左边界。请注意，数组中可能不包含 target ，这种情况可能导致以下两种结果。 插入点的索引 iii 越界。 元素 nums[i] 与 target 不相等。 当遇到以上两种情况时，直接返回 −1-1−1 即可。代码如下所示： 123456789def binary_search_left_edge(nums: list[int], target: int) -> int: """二分查找最左一个 target""" # 等价于查找 target 的插入点 i = binary_search_insertion(nums,...