数据结构与算法可视化：图解两数之和、二分查找与冒泡排序
原文：https://dev.to/nyaomaru/is-learning-dsa-boring-lets-use-dsa-view-view-two-sum-binary-search-and-bubble-sort-374o（作者 @nyaomaru）
你用过 DSA View View 吗？
DSA View View 能让你通过可视化代码的实际执行过程来理解数据结构与算法。
但仅仅介绍这个工具还不够。
它真的能帮助我们理解数据结构与算法吗？
在这篇文章中，我们将一起探讨三个经典问题：
- 两数之和
- 二分查找
- 冒泡排序
我们会先理解算法原理，然后通过 DSA View View 来观察实际发生了什么。
一起学习吧！
🗺️ 两数之和
让我们从一个非常著名的问题开始。
给定一个数字数组和一个目标值，找出数组中和为目标值的两个数字的索引。
例如，
nums = [2, 7, 11, 15]; target = 9;
答案是
[0, 1];
因为
2 + 7 = 9
很简单！
那么，我们应该如何找到它们呢？
暴力解法
最直接的方法大概是检查所有可能的配对。
function twoSum(nums: number[], target: number): number[] {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
}
这个方法可行。
但如果数组很大，我们可能需要进行大量的配对比较，对吧？
时间复杂度是 _O(n²)_。
我们能否避免重复检查相同的值？
可以。
我们使用一个 Map。
function twoSum(nums: number[], target: number): number[] {
const seen = new Map<number, number>();
for (let i = 0; i < nums.length; i++) {
const current = nums[i];
const need = target - current;
if (seen.has(need)) {
return [seen.get(need)!, i];
}
seen.set(current, i);
}
return [];
}
关键部分在这里 👇
const need = target - current;
与其问
我应该组合哪两个数字？
我们问
我需要什么数字来补全目标值？
让我们跟随示例来理解。
一开始
current = 2
target = 9
need = 9 - 2
= 7
我们之前见过 7 吗？
没有。
所以我们记下 2。
seen = {
2 → 0
}
接下来
current = 7
target = 9
need = 9 - 7
= 2
我们之前见过 2 吗？
见过！
seen = {
2 → 0
}
所以
return [0, 1];
完成了！
因为我们只需要遍历数组一次，时间复杂度变为：
时间复杂度: O(n) 空间复杂度: O(n)
👀 让我们来“看看”它
代码实现相当简洁。
但当我最初学习这个模式时，这部分感觉还是有点神奇。
if (seen.has(need))
need是从哪里来的？- 此时
seen里面是什么？ - 为什么检查之前的值就能解决问题？
这正是可视化能帮上忙的地方。
借助 DSA View View，我们可以一步一步地跟踪运行过程，查看值是如何变化的。
2 ↓ 需要 7 ↓ 记下 2 ↓ 7 ↓ 需要 2 ↓ 找到 2！
现在，Map 不再是什么神秘的技巧了。
我们完全可以理解这个思路。
记住我们已经看过的，然后检查我们需要的值是否存在。
不错！
🔍 二分查找
接下来是二分查找。
假设我们有这样一个有序数组
[1, 3, 5, 7, 9, 11, 13]
我们要查找
11
当然，可以从 1 开始逐个检查。
1 → 3 → 5 → 7 → 9 → 11
这当然可行。
但二分查找采取了更聪明的策略。
它不从头开始，而是从中间开始检查。
[1, 3, 5, 7, 9, 11, 13]
↑
mid
中间值是 7。
我们要找的是 11。
11 > 7
因为数组是有序的，我们立刻能推断出一条非常有用的信息。
7 左侧的所有值也都小于 11。
因此，我们不再需要考虑左半边了。👋
[1, 3, 5, 7, 9, 11, 13]
└───────┘
search
接下来检查剩余区间的中间值。
[9, 11, 13]
↑
mid
此时
11 === 11
找到了！🎉
以下是具体实现。
function binarySearch(nums: number[], target: number): number {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
return mid;
}
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
有三个关键变量。
left right mid
它们代表当前的搜索范围。
以我们的例子为开始状态：
left = 0 right = 6 mid = 3 [1, 3, 5, 7, 9, 11, 13] ↑ ↑ ↑ left mid right
由于
nums[mid] < target;
我们移动 left。
left = mid + 1;
现在变为
[1, 3, 5, 7, 9, 11, 13]
↑ ↑ ↑
left mid right
于是找到了 11。
为什么二分查找很快？
这是最有趣的部分。
每一步操作都排除了大约一半的剩余候选值。
假设有 1,000 个值，我们不一定需要检查 1,000 次。
它大致是这样一个过程
1000 ↓ 500 ↓ 250 ↓ 125 ↓ ...
因此二分查找具有
时间复杂度：O(log n) 空间复杂度：O(1)
但有一个非常重要的前提条件。
数据必须是有序的。
如果数据无序，我们就无法安全地丢弃一半的搜索范围。
让我们可视化一下
二分查找正是让我最初想要开发可视化工具的算法之一。
代码本身很短
left = mid + 1;
或者
right = mid - 1;
很简单。
但在学习时，我偶尔会疑惑：
等等... 我们现在搜索的是哪一部分？😿
当我们把 left、mid 和 right 可视化出来，思路就清晰多了。
我们并非随意修改三个数字。
而是在持续缩小搜索区域。
███████████████
↓
███████
↓
███
↓
█
这就是二分查找！
砍掉不需要的那一半。
然后再砍。再砍。再砍。
直到找到答案。✂️😸
冒泡排序
最后，我们来对一些东西进行排序！
考虑这个数组。
[5, 1, 4, 2, 8];
我们期望得到。
[1, 2, 4, 5, 8];
冒泡排序反复比较 两个相邻的值。
如果它们的顺序错了，就交换它们。
让我们看看开头部分。
[5, 1, 4, 2, 8] ↑ ↑
比较
5 > 1
因此交换它们。
[1, 5, 4, 2, 8]
接下来
[1, 5, 4, 2, 8]
↑ ↑
再次
5 > 4
交换！
[1, 4, 5, 2, 8]
并继续。
[1, 4, 5, 2, 8]
↑ ↑
5 > 2
交换！
[1, 4, 2, 5, 8]
最终，较大的值会向数组的末尾移动。
它们有点像是...
冒泡上去了。这就是它被称为 冒泡排序 的原因。
下面是一个简单的实现：
function bubbleSort(nums: number[]): number[] {
for (let i = 0; i < nums.length - 1; i++) {
for (let j = 0; j < nums.length - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
[nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
}
}
}
return nums;
}
我们反复比较
nums[j];
和
nums[j + 1];
并在必要时交换它们。
经过一轮完整的遍历后，剩余的最大值会到达其末尾附近的正确位置。
所以在下一轮遍历中，我们不需要再检查那个位置。
这就是为什么内层循环包含
nums.length - i - 1;
复杂度
冒泡排序对大数组来说速度不快。
它的时间复杂度是
时间：O(n²) 空间：O(1)
所以我大概不会明天就突然用冒泡排序替换生产环境的排序算法。但作为一个学习示例，我真的很喜欢它。
为什么？
因为你可以 看到算法在工作。
用 View View 看看
这可能是三个算法中视觉上最令人满意的。
我们不只是阅读
[nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
我们可以跟随这些值在数组中移动。
[5, 1, 4, 2, 8]
↓ 交换
[1, 5, 4, 2, 8]
↓ 交换
[1, 4, 5, 2, 8]
↓ 交换
[1, 4, 2, 5, 8]
然后下一轮遍历开始。
代码包含嵌套循环、索引、比较和交换。
但从视觉上看，基本规则极其简单：
比较相邻元素。如果左边的更大，就交换它们。
重复。重复。重复。
排序完成！
我们到底学到了什么？
这三个问题看起来大不相同。
但每个问题都引入了一种有用的思维方式。
两数之和
记住之前步骤中的信息。
我已经见过我需要的东西吗？
二分查找
利用我们已知的信息来排除不可能的候选者。
我能安全地丢弃一半的搜索空间吗？
冒泡排序
将一个更大的问题分解成许多小的比较。
这两个值的顺序正确吗？
这是我觉得学习数据结构与算法有趣的地方之一。
起初，实现看起来可能像是一堆索引、循环、条件和神秘变量的集合。
但在代码背后，通常有一个简单得多的核心思想。
有时我只盯着代码并不能完全理解那个思想。
我想 把它看出来。
结论
在这篇文章中，我们研究了三个经典算法：
- 使用
Map的两数之和 - 二分查找
- 冒泡排序
更重要的是，我们观察了 数据在算法运行时如何变化。
我认为这就是可视化特别有用的地方。
- 阅读最终的实现告诉我们 代码是什么。
- 逐步调试它有助于我们理解 它为什么有效。
这正是我构建 DSA View View 的原因。
{% embed https://dsa-view-view.vercel.app %}
你可以编写或加载一个 TypeScript 实现，使用自己的输入运行它，并在运行时前后移动步骤。
如果你也在学习数据结构与算法，可以尝试拿一个你已经解决过的问题，然后一步步地查看它。
你可能会注意到一些只阅读代码时没有注意到的东西。
如果你有希望我接下来讲解的算法问题，请在评论中告诉我！
我自己还有很多算法需要学习。
让我们一起锻炼数据结构与算法这块肌肉吧！
原文：https://dev.to/nyaomaru/is-learning-dsa-boring-lets-use-dsa-view-view-two-sum-binary-search-and-bubble-sort-374o（作者 @nyaomaru）