柒书
博客
工具
收藏
游戏
博客
工具
收藏
游戏

经典算法

排序

快速排序

function quickSort(arr) {
    if (arr.length < 2) return arr;
    let pivot = arr[0];
    let left = arr.slice(1).filter(x => x <= pivot);
    let right = arr.slice(1).filter(x => x > pivot);
    return [...quickSort(left), pivot, ...quickSort(right)];
}
  • 优点：
    • 效率高：在平均情况下，快速排序的时间复杂度为 O(n log ⁡n)
    • 内存使用少,适用于多种数据类型
    • 缓存友好
  • 缺点：
    • 最坏情况时间复杂度较高，极端情况其时间复杂度会退化到 O(n^2)
    • 不稳定，相同值的元素可能会改变它们原始的相对顺序
    • 递归风险：因为快速排序依赖于递归来解决问题，所以在处理特别大的数据集时，可能会遇到栈溢出的问题。

为了解决递归风险问题可以考虑使用迭代的方式:

function quickSortIterative(arr) {
   // 如果数组长度小于2，则直接返回（因为已经排序好了）
   if (arr.length < 2) return arr;
   // 使用栈来保存需要排序的子数组的起始和结束索引
   let stack = [[0, arr.length - 1]];
   while (stack.length > 0) {
       // 弹出栈顶元素，获取当前需要排序的子数组的起始和结束索引
       let [low, high] = stack.pop();
       if (low < high) {
           // 在当前子数组中选择一个基准值，并进行分区操作
           let pivotIndex = partition(arr, low, high);
           // 将左右两个新的子数组的起始和结束索引压入栈中
           stack.push([low, pivotIndex - 1], [pivotIndex + 1, high]);
       }
   }

   return arr;
}

function partition(arr, low, high) {
   let pivot = arr[high]; // 选择最后一个元素作为基准
   let i = low - 1; // i是较小元素的索引
   for (let j = low; j < high; j++) {
       // 如果当前元素小于或等于pivot，则交换位置
       if (arr[j] <= pivot) {
           i++;
           [arr[i], arr[j]] = [arr[j], arr[i]]; // 交换元素
       }
   }
   // 把基准元素放到正确的位置
   [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
   // 返回基准元素的位置
   return i + 1;
}

归并排序

function mergeSort(arr) {
   if (arr.length < 2) 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) {
   let result = [];
   while (left.length && right.length) {
       if (left[0] <= right[0]) {
           result.push(left.shift())
       } else {
           result.push(right.shift())
       }
   }
   return result.concat(left, right);
}
  • 优点：
    • 稳定性：归并排序是一种稳定排序算法，相同值的元素在排序后仍然保持它们原始的相对顺序。
    • 时间复杂度一致性：时间复杂度始终为 O(n log ⁡n)
    • 适合链表排序
    • 易于实现并行化
  • 缺点：
    • 空间复杂度较高，其空间复杂度为O(n)
    • 常数因子较大，于较小规模的数据集，归并排序可能不如快速排序快。
    • 递归风险：在最坏的情况下，归并排序的递归深度可达O(log ⁡n)，可能会遇到栈溢出的问题。

解决递归风险的一种方案(需要更大的空间):

function mergeSortIterative(arr) {
    if (arr.length < 2) return arr;
    // 初始化一个数组，每个元素代表需要排序的子数组，初始时是数组中每个单独的元素
    let queue = arr.map(item => [item]);
    // 当queue中有多个子数组时，继续合并
    while (queue.length > 1) {
        let newQueue = [];
        // 每次从queue中取出两个子数组进行合并
        for (let i = 0; i < queue.length; i += 2) {
            let left = queue[i];
            let right = i + 1 < queue.length ? queue[i + 1] : [];
            newQueue.push(merge(left, right));
        }
        queue = newQueue;
    }
    return queue[0];
}

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

交集问题

function binarySearch(arr, target) {
    let start = 0;
    let end = arr.length - 1;
    while (start <= end) {
        const mid = Math.floor((start + end) / 2);
        if (arr[mid] === target) {
            return true;
        } else if (arr[mid] < target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return false
}


function intersection(arr, arr2) {
    let result = []
    arr.sort((a, b) => a - b)
    for (let key of arr2) {
        if (binarySearch(arr, key) && !result.includes(key)) {
            result.push(key)
        }
    }
    return result
}
  • 适用于解决排班冲突等问题

动态规划

核心思想：空间换时间，通过前一步的计算结果快速得出下一步结果

斐波拉契数列

TIP

斐波那契数列的定义是：从第三项开始，每一项都等于前两项之和。具体来说，斐波那契数列的前几项为：0、1、1、2、3、5、8、13、21、34……

function fib(n) {
    const fibs = [0, 1];
    for (let i = 2; i <= n; i++) {
        fibs[i] = fibs[i - 1] + fibs[i - 2]
    }
    return fibs[n];
}

最长字串问题

const longestCommonSubsequence = function (text1, text2) {
    const m = text1.length, n = text2.length;
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        const c1 = text1[i - 1];
        for (let j = 1; j <= n; j++) {
            const c2 = text2[j - 1];
            if (c1 === c2) {
                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[m][n];
};