一、 排序算法

1.1 冒泡排序

1.1.1.原理

通过重复遍历待排序的元素，比较相邻的元素并交换它们的位置，直到没有需要交换的元素。

1.1.2.代码实现

function bubbleSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n-1; i++) {
        for (let j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]]; // 交换
            }
        }
    }
    return arr;
}

1.1.3实际应用场景

1. 小型数据集排序

• 场景描述：当数据集非常小（例如少于10个元素）时，冒泡排序的性能开销相对较小，且实现简单。
• 应用示例：在一个简单的表单中，用户输入的几个数字需要进行排序，使用冒泡排序可以快速实现。

2. 教学和学习

• 场景描述：冒泡排序是排序算法中最基础的一种，常用于教学和学习排序算法的入门。
• 应用示例：在编程课程或教程中，通过实现冒泡排序来帮助学生理解排序的基本概念和算法逻辑。

3. 动态排序

• 场景描述：在某些需要实时排序的场景中，冒泡排序可以用于动态更新排序结果。
• 应用示例：在一个实时更新的排行榜中，每次有新数据加入时，使用冒泡排序来快速更新排序结果。

4. 简单排序需求

• 场景描述：在一些简单的排序需求中，冒泡排序可以满足需求，且实现简单。
• 应用示例：在一个简单的待办事项列表中，用户可以手动调整事项的顺序，使用冒泡排序来实现顺序的调整。

5. 性能不敏感的场景

• 场景描述：在某些性能不敏感的场景中，冒泡排序可以作为一种简单的解决方案。
• 应用示例：在一个简单的个人博客中，文章列表的排序可以使用冒泡排序，因为文章数量通常不会太多。

6. 前端调试和测试

• 场景描述：在前端开发中，冒泡排序可以用于调试和测试排序功能的正确性。
• 应用示例：在开发过程中，使用冒泡排序来验证其他排序算法的正确性，或者用于测试排序功能的边界条件。

---

1.2 选择排序

原理：每次从未排序部分选择最小的元素，放到已排序部分的末尾。

代码实现：

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;
            }
        }
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; // 交换
    }
    return arr;
}

1.3 插入排序

原理：将元素分为已排序和未排序两部分，逐个将未排序的元素插入到已排序部分。

代码实现：

function insertionSort(arr) {
    let n = arr.length;
    for (let i = 1; i < n; i++) {
        let key = arr[i];
        let j = i-1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

1.4 快速排序

原理：选择一个基准元素，将数组分成两部分，比基准小的在左边，大的在右边，然后递归排序这两部分。

代码实现：

function quickSort(arr) {
    if (arr.length <= 1) return arr;
    let pivot = arr[arr.length - 1];
    let left = arr.filter(x => x < pivot);
    let right = arr.filter(x => x > pivot);
    return [...quickSort(left), pivot, ...quickSort(right)];
}

1.5 归并排序

原理：将数组分成两半，分别排序再合并成一个有序数组。

代码实现：

function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    return merge(left, right);
}

function merge(left, right) {
    const result = [];
    let i = 0, j = 0;
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }
    return result.concat(left.slice(i)).concat(right.slice(j));
}

二、 查找算法

2.1 二分查找

原理：适用于已排序数组，通过不断将查找范围减半来快速找到目标值。

代码实现：

function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1; // 未找到
}

2.2 线性查找

原理：逐个检查元素，直到找到目标或遍历完整个数组。

代码实现：

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return -1; // 未找到
}

三、字符串操作

3.1 字符串反转

代码实现：

function reverseString(str) {
    return str.split('').reverse().join('');
}

3.2 判断回文字符串

代码实现：

function isPalindrome(str) {
    const reversed = str.split('').reverse().join('');
    return str === reversed;
}

3.3 字符串替换

代码实现：

function replaceString(str, target, replacement) {
    return str.split(target).join(replacement);
}

3.4 字符串分割

代码实现：

function splitString(str, delimiter) {
    return str.split(delimiter);
}

四、数组操作

4.1 合并两个有序数组

代码实现：

function mergeSortedArrays(arr1, arr2) {
    const result = [];
    let i = 0, j = 0;
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] < arr2[j]) {
            result.push(arr1[i++]);
        } else {
            result.push(arr2[j++]);
        }
    }
    return result.concat(arr1.slice(i)).concat(arr2.slice(j));
}

4.2 寻找数组中的最大/最小值

代码实现：

function findMinMax(arr) {
    if (arr.length === 0) return {};
    let min = arr[0], max = arr[0];
    for (const num of arr) {
        if (num < min) min = num;
        if (num > max) max = num;
    }
    return { min, max };
}

4.3 删除数组中的重复元素

代码实现：

function removeDuplicates(arr) {
    return [...new Set(arr)];
}

4.4 旋转数组

代码实现：

function rotateArray(arr, k) {
    k = k % arr.length; // 处理k大于数组长度的情况
    return arr.slice(-k).concat(arr.slice(0, arr.length - k));
}

五、 栈和队列

5.1 实现栈（使用数组）

代码实现：

class Stack {
    constructor() {
        this.items = [];
    }
    push(item) {
        this.items.push(item);
    }
    pop() {
        return this.items.pop();
    }
    peek() {
        return this.items[this.items.length - 1];
    }
    isEmpty() {
        return this.items.length === 0;
    }
}

5.2 实现队列（使用数组）

代码实现：

class Queue {
    constructor() {
        this.items = [];
    }
    enqueue(item) {
        this.items.push(item);
    }
    dequeue() {
        return this.items.shift();
    }
    front() {
        return this.items[0];
    }
    isEmpty() {
        return this.items.length === 0;
    }
}

5.3 括号匹配问题

代码实现：

function isValidParentheses(str) {
    const stack = [];
    const matchingBrackets = { '(': ')', '{': '}', '[': ']' };
    
    for (const char of str) {
        if (matchingBrackets[char]) {
            stack.push(char);
        } else if (Object.values(matchingBrackets).includes(char)) {
            if (matchingBrackets[stack.pop()] !== char) return false;
        }
    }
    return stack.length === 0;
}

六、动态规划

6.1 Fibonacci数列

代码实现：

function fibonacci(n) {
    if (n <= 1) return n;
    let a = 0, b = 1;
    for (let i = 2; i <= n; i++) {
        let temp = a;
        a = b;
        b = temp + b;
    }
    return b;
}

6.2 最长公共子序列

代码实现：

function longestCommonSubsequence(text1, text2) {
    const dp = Array.from({ length: text1.length + 1 }, () => Array(text2.length + 1).fill(0));
    
    for (let i = 1; i <= text1.length; i++) {
        for (let j = 1; j <= text2.length; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[text1.length][text2.length];
}

6.3 0-1背包问题

代码实现：

function knapsack(weights, values, capacity) {
    const n = weights.length;
    const dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));

    for (let i = 1; i <= n; i++) {
        for (let w = 1; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][capacity];
}

七、树和图

7.1 二叉树遍历（前序、中序、后序）

代码实现：

class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

function preorderTraversal(root) {
    if (!root) return [];
    return [root.value, ...preorderTraversal(root.left), ...preorderTraversal(root.right)];
}

function inorderTraversal(root) {
    if (!root) return [];
    return [...inorderTraversal(root.left), root.value, ...inorderTraversal(root.right)];
}

function postorderTraversal(root) {
    if (!root) return [];
    return [...postorderTraversal(root.left), ...postorderTraversal(root.right), root.value];
}

7.2 最小生成树（Kruskal或Prim算法）

Kruskal算法的代码实现：

function kruskal(nodes, edges) {
    edges.sort((a, b) => a[2] - b[2]); // 按权重排序
    const parent = Array(nodes).fill(0).map((_, index) => index);
    
    function find(x) {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    function union(x, y) {
        const rootX = find(x);
        const rootY = find(y);
        if (rootX !== rootY) {
            parent[rootX] = rootY; // 合并集合
        }
    }

    const result = [];
    for (const [u, v, w] of edges) {
        if (find(u) !== find(v)) {
            union(u, v);
            result.push([u, v, w]);
        }
    }
    return result;
}

7.3 图的深度优先搜索（DFS）与广度优先搜索（BFS）

DFS代码实现：

function dfs(graph, start, visited = new Set()) {
    if (visited.has(start)) return;
    visited.add(start);
    console.log(start); // 或者其他处理
    for (const neighbor of graph[start]) {
        dfs(graph, neighbor, visited);
    }
}

BFS代码实现：

function bfs(graph, start) {
    const visited = new Set();
    const queue = [start];
    
    while (queue.length > 0) {
        const node = queue.shift();
        if (!visited.has(node)) {
            console.log(node); // 或者其他处理
            visited.add(node);
            queue.push(...graph[node]);
        }
    }
}

八、位运算

8.1 查找一个数的二进制中1的个数

代码实现：

function countOnes(n) {
    let count = 0;
    while (n > 0) {
        count += n & 1; // 取最后一位
        n >>= 1; // 右移
    }
    return count;
}

8.2 判断一个数是否为2的幂

代码实现：

function isPowerOfTwo(n) {
    return n > 0 && (n & (n - 1)) === 0;
}

九、基本数学题

9.1 判断素数

代码实现：

function isPrime(num) {
    if (num <= 1) return false;
    for (let i = 2; i <= Math.sqrt(num); i++) {
        if (num % i === 0) return false;
    }
    return true;
}

9.2 最大公约数（Euclidean算法）

代码实现：

function gcd(a, b) {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return a;
}

9.3 最小公倍数

代码实现：

function lcm(a, b) {
    return (a * b) / gcd(a, b);
}

十、 LRU缓存算法

代码实现：

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map(); // 使用Map保存键值对以保持插入顺序
    }
    
    get(key) {
        if (!this.cache.has(key)) return -1;
        const value = this.cache.get(key);
        this.cache.delete(key); // 删除后再插入以更新顺序
        this.cache.set(key, value);
        return value;
    }
    
    put(key, value) {
        if (this.cache.has(key)) {
            this.cache.delete(key); // 删除后再插入以更新顺序
        } else if (this.cache.size >= this.capacity) {
            // 弹出最久未使用的条目
            this.cache.delete(this.cache.keys().next().value);
        }
        this.cache.set(key, value);
    }
}

        以上是常见的算法和数据结构的详细介绍以及代码实现示例。你可以根据需要调整和使用这些实现。