一、理解算法
算法是一组定义明确的指令或步骤，用于解决特定问题或执行某项任务，它可以是简单的计算过程，也可以是复杂的逻辑运算。算法是计算机科学的核心，它能帮助计算机高效地处理数据、执行任务和解决问题。
二、算法五大特性
- 输入：算法可以有零个或多个输入，输入是算法操作的数据。所谓零个输入是指算法本身给定了初始条件。
- 输出：算法至少有一个输出。输出是算法处理输入后产生的结果。
- 有限性：一个算法必须保证在有限的步骤内完成。
- 有效性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限资源限制下完成。
- 确切性： 一个算法的每一步骤必须有确切的定义，不能有歧义。
三、算法应用场景
搜索引擎：搜索引擎使用算法对搜索结果进行排序，以便显示最相关的网页
电子商务：根据用户的购买历史、浏览行为和偏好，推荐可能感兴趣的商品
社交媒体：根据用户的兴趣和行为推荐内容，精准投放广告，提高广告的点击率和转化率。
金融服务：自动化执行复杂的金融交易策略，提高交易效率和准确性。
导航系统：通过算法提供实时导航建议，避开拥堵路段，选择最优路线。
四、理解数据结构
数据结构是计算机存储、组织数据的方式，是指相互之间存在特定关系的数据元素的集合。
数据元素相互之间的关系称为结构，根据关系的不同特性，通常有如下四类基本的结构：
- 集合结构：该结构的数据元素间的关系是“属于同一个集合”
- 线性结构：该结构的数据元素之间存在着一对一的关系
- 树型结构：该结构的数据元素之间存在着一对多的关系
- 网状结构：该结构的数据元素之间存在着多对多的关系
五、常见的数据结构
1. 数组（Array）
- 特性：数组是一种线性数据结构，元素存储在连续的内存位置中，可以通过索引快速访问。
- 应用：
- 列表渲染：在React或Vue等框架中，数组常用于渲染列表项。
- 数据操作：常用在数据过滤、排序和映射等操作。
- 缓存：可以用于缓存数据，提高访问速度。
2. 链表（Linked List）
- 特性：链表是一种线性数据结构，元素存储在节点中，每个节点包含数据和指向下一个节点的指针。
- 应用：
- 动态数据管理：适用于需要频繁插入和删除元素的场景。
- 实现队列和栈：可以用来实现队列和栈的数据结构。
// 定义链表节点类
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// 定义链表类
class LinkedList {
constructor() {
this.head = null;
}
// 插入节点到链表尾部
append(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
// 插入节点到链表头部
prepend(data) {
const newNode = new Node(data);
newNode.next = this.head;
this.head = newNode;
}
// 删除指定值的节点
delete(data) {
if (!this.head) return;
if (this.head.data === data) {
this.head = this.head.next;
return;
}
let current = this.head;
let previous = null;
while (current && current.data !== data) {
previous = current;
current = current.next;
}
if (current) {
previous.next = current.next;
}
}
// 查找节点
find(data) {
let current = this.head;
while (current) {
if (current.data === data) {
return current;
}
current = current.next;
}
return null;
}
// 打印链表
printList() {
let current = this.head;
let listValues = [];
while (current) {
listValues.push(current.data);
current = current.next;
}
console.log(listValues.join(' -> '));
}
}
3. 栈（Stack）
- 特性：栈是一种后进先出（LIFO, Last In First Out）的数据结构，只允许在一端进行插入和删除操作。
- 应用：
- 浏览器历史记录：浏览器的历史记录可以看作是一个栈。
- 表达式求值：用于实现表达式的计算，如中缀表达式转后缀表达式。
class Stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element);
}
pop() {
return this.items.pop();
}
peek() {
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
printStack() {
console.log(this.items.join(' -> '));
}
}4. 队列（Queue）
- 特性：队列是一种先进先出（FIFO, First In First Out）的数据结构，只允许在一端插入元素，在另一端删除元素。
- 应用：
- 任务调度：用于管理异步任务的执行顺序。
- 打印队列：管理打印任务的顺序。
class Queue {
constructor() {
this.items = [];
}
enqueue(element) {
this.items.push(element);
}
dequeue() {
return this.items.shift();
}
front() {
return this.items[0];
}
isEmpty() {
return this.items.length === 0;
}
printQueue() {
console.log(this.items.join(' -> '));
}
}5. 树（Tree）
- 特性：树是一种层次结构的数据结构，由节点组成，每个节点有零个或多个子节点。
- 应用：
- 文件系统：用于表示文件和目录的层次结构。
- DOM操作：浏览器的文档对象模型（DOM）本身就是一个树结构。
- 数据分类：用于实现分类和层次结构的数据展示。
6. 图（Graph）
- 特性：图是一种非线性数据结构，由节点（顶点）和边组成，边可以是有向的或无向的。
- 应用：
- 社交网络：用于表示用户之间的关系。
- 路径查找：用于查找最短路径或推荐路径，如Google Maps的路线规划。
- 依赖关系：用于管理模块或组件之间的依赖关系。
7. 哈希表（Hash Table）
- 特性：哈希表是一种通过哈希函数将键映射到存储地址的数据结构，允许以平均常数时间复杂度进行插入、删除和查找操作。
- 应用：
- 缓存机制：用于缓存数据，提高访问速度。
- 快速查找：用于实现快速的键值对查找。
- 去重：用于去重操作。
8. 集合（Set）
- 特性：集合是一种无序且不重复的数据结构，通常支持插入、删除和查找操作。
- 应用：
- 去重：用于去除数组中的重复元素。
- 集合操作：实现集合的并集、交集和差集操作。
9. 堆（Heap）
- 特性：堆是一种特殊的树结构，通常用于实现优先队列。
- 应用：
- 优先队列：用于实现优先级队列，如任务调度系统。
- 排序算法：如堆排序算法。
六、排序算法
排序是程序开发中非常常见的操作，对一组任意的数据元素经过排序操作后，就可以把他们变成一组一定规则排序的有序序列。
对与排序算法的好坏衡量，主要是从时间复杂度、空间复杂度、稳定性来判断。稳定性是指在待排序的记录序列中，存在多个具有相同关键字的记录，经过排序后，这些记录的相对顺序保持不变。
七、常见的排序算法
常见的排序算法有：
- 冒泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
冒泡排序
一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来
思路如下：
比较相邻的元素，如果第一个比第二个大，就交换它们两个
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数
针对所有的元素重复以上的步骤，除了最后一个
重复上述步骤，直到没有任何一堆数字需要比较
function bubbleSort(arr) { let n = arr.length; let swapped; // 外层循环控制遍历的轮数 for (let i = 0; i < n - 1; i++) { swapped = false; // 内层循环进行相邻元素的比较和交换 for (let j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { // 交换元素 [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; swapped = true; } } // 如果没有发生交换，说明数组已经排序完成 if (!swapped) { break; } } return arr; } // 示例使用 const arr = [38, 27, 43, 3, 9, 82, 10]; const sortedArr = bubbleSort(arr); console.log(sortedArr); // 输出: [3, 9, 10, 27, 38, 43, 82]
选择排序
选择排序是一种简单直观的排序算法，它也是一种交换排序算法
无论什么数据进去都是
O(n²)的时间复杂度。所以用到它的时候，数据规模越小越好唯一的好处是不占用额外的内存存储空间
思路如下：
- 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
- 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复第二步，直到所有元素均排序完毕
function selectionSort(arr) { let n = arr.length; // 外层循环控制已排序部分的末尾位置 for (let i = 0; i < n - 1; i++) { // 假设当前元素是未排序部分的最小元素 let minIndex = i; // 内层循环找到未排序部分的最小元素 for (let j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } // 如果找到的最小元素不是当前元素，则交换 if (minIndex !== i) { [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; } } return arr; } // 示例使用 const arr = [38, 27, 43, 3, 9, 82, 10]; const sortedArr = selectionSort(arr); console.log(sortedArr); // 输出: [3, 9, 10, 27, 38, 43, 82]
插入排序
插入排序是一种简单直观的排序算法，工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
解决思路如下：
- 把待排序的数组分成已排序和未排序两部分，初始的时候把第一个元素认为是已排好序的
- 从第二个元素开始，在已排好序的子数组中寻找到该元素合适的位置并插入该位置（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
- 重复上述过程直到最后一个元素被插入有序子数组中
function insertionSort(arr) { const len = arr.length; let preIndex, current; // 从第二个元素开始，从未排序部分取出一个元素 for (let i = 1; i < len; i++) { preIndex = i - 1; // 已排序部分的最后一个元素的索引 current = arr[i]; // 当前要插入的元素 // 将取出的元素插入到已排序部分的正确位置 while(preIndex >= 0 && arr[preIndex] > current) { arr[preIndex+1] = arr[preIndex]; preIndex--; } arr[preIndex+1] = current; // 插入到正确的位置 } return arr; } // 示例使用 const arr = [38, 27, 43, 3, 9, 82, 10]; const sortedArr = insertionSort(arr); console.log(sortedArr); // 输出: [3, 9, 10, 27, 38, 43, 82]
归并排序
归并排序（Merge Sort）是一种高效的、稳定的、基于分治法的排序算法。其基本思想是将数组分成两个子数组，分别对这两个子数组进行排序，然后将排序好的子数组合并成一个有序的数组。归并排序的时间复杂度为 O(n logn)，适用于需要稳定排序的场景。
思路如下：
- 分解：将数组分成两个子数组，直到每个子数组只包含一个元素或为空。
- 合并：将两个子数组合并成一个有序的数组。合并时，从两个子数组的起始位置开始比较，将较小的元素放入结果数组中，然后移动指针继续比较，直到所有元素都被合并到结果数组中。
function mergeSort(arr) { // 如果数组长度小于等于1，则不需要排序，直接返回 if (arr.length <= 1) { return arr; } // 找到数组的中间位置 const mid = Math.floor(arr.length / 2); // 将数组分成两部分 const left = arr.slice(0, mid); const right = arr.slice(mid); // 递归地对两部分进行排序 const sortedLeft = mergeSort(left); const sortedRight = mergeSort(right); // 合并两个有序的子数组 return merge(sortedLeft, sortedRight); } function merge(left, right) { let result = []; let leftIndex = 0; let rightIndex = 0; // 比较两个子数组的元素，将较小的元素放入结果数组 while (leftIndex < left.length && rightIndex < right.length) { if (left[leftIndex] < right[rightIndex]) { result.push(left[leftIndex]); leftIndex++; } else { result.push(right[rightIndex]); rightIndex++; } } // 如果左子数组还有剩余元素，将其全部放入结果数组 while (leftIndex < left.length) { result.push(left[leftIndex]); leftIndex++; } // 如果右子数组还有剩余元素，将其全部放入结果数组 while (rightIndex < right.length) { result.push(right[rightIndex]); rightIndex++; } return result; } // 示例使用 const arr = [38, 27, 43, 3, 9, 82, 10]; const sortedArr = mergeSort(arr); console.log(sortedArr); // 输出: [3, 9, 10, 27, 38, 43, 82]
快速排序
快速排序（Quick Sort）是一种高效的、基于分治法的排序算法。其基本思想是选择一个“基准”元素，通过一趟排序将数组分成两部分，其中一部分的所有元素都比基准元素小，另一部分的所有元素都比基准元素大，然后递归地对这两部分进行排序。快速排序的平均时间复杂度为 O(nlogn)，但在最坏情况下（例如，每次选择的基准都是当前数组的最大或最小元素）时间复杂度为 O(n^2)。
思路如下：
- 选择基准（Pivot）：从数组中选择一个元素作为基准。选择基准的方法有多种，可以是第一个元素、最后一个元素、随机选择一个元素或选择中间位置的元素。
- 分区（Partition）：将数组分成两部分，一部分的所有元素都小于基准，另一部分的所有元素都大于基准。
- 递归排序：递归地对分区后的两部分分别进行快速排序。
function quickSort(arr, left = 0, right = arr.length - 1) { if (left < right) { // 找到分区的位置 const pivotIndex = partition(arr, left, right); // 递归地对左边和右边进行排序 quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex + 1, right); } return arr; } function partition(arr, left, right) { // 选择最右边的元素作为基准 const pivot = arr[right]; let i = left - 1; // 遍历数组，将小于基准的元素移到左边 for (let j = left; j < right; j++) { if (arr[j] < pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; // 交换元素 } } // 将基准元素放到正确的位置 [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]]; // 交换元素 return i + 1; } // 示例使用 const arr = [38, 27, 43, 3, 9, 82, 10]; const sortedArr = quickSort(arr); console.log(sortedArr); // 输出: [3, 9, 10, 27, 38, 43, 82]
八、二分查找
二分查找算法，也称折半搜索算法，是一种在有序数组中查找某一特定元素的搜索算法。
- 前提条件：数组必须是已排序的（升序或降序）。
- 工作原理：通过每次将搜索范围减半来快速找到目标值。
- 时间复杂度：O(log n)，其中n是数组的长度。这是因为每次查找都将搜索范围缩小一半。
- 空间复杂度：O(1)，因为二分查找只需要常数级别的额外空间。
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
let result = -1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
result = mid; // 找到目标值，记录索引
right = mid - 1; // 继续向左查找
} else if (arr[mid] < target) {
left = mid + 1; // 目标值在右半部分
} else {
right = mid - 1; // 目标值在左半部分
}
}
return result; // 返回第一个出现的位置
}
// 示例使用
const arr = [1, 3, 5, 7, 9, 9, 9, 11, 13, 15];
const target = 9;
const indexFirst = binarySearchFirst(arr, target);
console.log(indexFirst); // 输出: 4