算法和数据结构简介（Javascript 版）

介绍

了解算法和数据结构对于将您的绩效提高 10 倍于不了解的同行至关重要。这是因为您批判性地分析问题并设计解决问题的最佳方法。这可能意味着加快服务器请求时间或找到以最小磁盘空间存储大型数据集的最佳方式。

本文旨在帮助您了解算法和数据结构的基本概念以及如何使用 JavaScript 实现它们。

什么是算法？算法是用于完成任务的逐步指令集。假设你有一个早起的问题，你总是错过最后期限。你如何解决这个问题？啊哈！设置闹钟。这就是算法的样子。

另一方面，数据结构是有效存储数据的方法。

数据结构和算法 (DSA) 非常重要，以至于它们对计算机的整体性能至关重要。您选择的算法将决定其运行时间（Big O Notation）或效率。一些流行的 DSA 是二进制搜索、递归、排序、数组、链表和哈希表。

什么是二分搜索？

假设您正在一个国家/地区的目录中搜索一个名称；它以 J 开头。您可以从头开始（从“A”个国家/地区开始）并不断翻页，直到您到达“J”个国家/地区列表（这些国家/地区按字母顺序排序）。如果国家/地区以“Z”开头，那么您会一直翻到目录的末尾。这被称为简单搜索算法。但是想象一下，如果这是一个包含超过 100,000 个电话号码的电话簿目录，这将是难以想象的。你如何优化这个？二进制搜索来救援。

二进制搜索算法将元素的排序列表作为输入，如果您要查找的元素在列表中，则二进制搜索返回它所在的位置，否则返回 null。二分搜索不是一步一步到达日本，而是将这个数组分成多个部分并相应地搜索每个部分。

这样，搜索速度很快。

数组

它们是由键索引的元素的集合。数组元素按顺序存储，键作为集合中的标识符。它的索引从 0 开始。

它们非常有用，因为检索或排序任何元素需要固定时间 O(1)。它还可以用于实现许多其他数据结构，这些数据结构对数据的操作方式施加了额外的限制。例如，字符串可以实现为字符数组。

这是 JavaScript 中数组和二进制搜索的实现。

 function binary_search(list, item) { let guess = list.find(element => element == item); if (guess) { return guess + "\ncountry index no: " + list.findIndex(country => country === guess); } return null + ": element is not in the array" } console.log(binary_search(country_list, 'Japan')); // Japan | country index no: 109 console.log(binary_search(country_list, 'Cookie')); // null: element is not in the array

排序算法

程序员很少使用排序。它主要由他们编码的语言或库处理。例如，JavaScript 语言使用插入排序、堆排序或快速排序对数组进行排序。

Heapsort 类似于 Javascript 数组过滤方法。它将输入划分为已排序区域和未排序区域，并迭代地将元素移动到已排序区域。这是一个例子；

链表

链表是一种数据结构，其中每个元素都包含数据和指向列表中下一个元素的指针。链表的一个显着特点是它的项目可以分散在内存中的任何地方。这不适用于数组。请参阅下面的一些示例；

什么是哈希表？

哈希表是数组中任意元素的列表。要存储的元素或其键用作数组中的索引。这是一个例子：

散列函数将要放置的元素的键转换为散列，然后将散列后的元素映射到表中的指定位置。这些元素中的每一个也可以是表中任意元素的子数组。

递归

递归是许多其他算法中使用的一种编码技术。它是冗长代码的捷径，除了程序员之外可能不会提供任何性能提升。

假设你找到了一个宝箱。要解锁这种情况，您需要从带有其他小盒子的盒子中取出钥匙，这些盒子中可能还有其他盒子。

一种方法是制作一堆要搜索的框列表，然后逐个查看这些框。如果你找到钥匙，太好了！如果没有，则将新的空框添加到堆列表中以供稍后搜索。

递归删除了将找到的新空框添加到搜索列表的步骤。它立即在新找到的空框上调用搜索方法。这是 Javascript 中的示例；

 const suitCase = new Map(); suitCase.set('box-0', '') .set('box-1', '') .set('box-2', '') .set('box-3', '') .set('box-4', 'key') .set('box-5', '') .set('box-6', ''); function search (suit) { for (let [key, value] of suit) { if (value === 'key') { console.log(`Found ${value} at ${key}!`); } } } search(suitCase); // prints Found key at box-4!

你找到了钥匙，多田！

总之，DSA 是作为程序员有效思考的好方法。它为您提供解决难题的工具。单击 GitHub 存储库链接以下载本文中使用的所有代码片段。快乐黑客！

GitHub 代码库