前端进阶必修课：JS排序算法全家桶，让你面试Offer拿到手软！

在前端开发中，数据处理是家常便饭。而排序算法，作为数据处理的基础，不仅是面试的常客，更是提升代码效率的关键。今天，我们就用 JavaScript 来实现几种经典的排序算法，让你彻底掌握它们，面试 Offer 拿到手软！

一、排序算法的重要性

排序算法，简单来说，就是将一组数据按照特定的顺序（例如升序或降序）排列。在实际开发中，排序的应用场景非常广泛：

• 数据展示： 将商品列表、用户列表等按照价格、时间、评分等排序。
• 搜索优化： 快速定位目标数据，提高搜索效率。
• 数据分析： 为数据分析提供基础，方便挖掘数据价值。

掌握排序算法，不仅能让你写出更高效的代码，还能在面试中脱颖而出。

二、经典排序算法详解

接下来，我们用 JavaScript 来实现几种常见的排序算法，并分析它们的优缺点。

1. 冒泡排序（Bubble Sort）

• 原理： 比较相邻的元素，如果顺序错误就交换它们。重复这个过程，直到没有需要交换的元素。
• 特点： 简单易懂，但效率较低，时间复杂度为 O(n^2)。
• JS实现：

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    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]];
      }
    }
  }
  return arr;
}

// 测试
const arr = [5, 2, 8, 1, 9, 4];
console.log("冒泡排序结果：", bubbleSort(arr)); // 输出：[1, 2, 4, 5, 8, 9]

2. 选择排序（Selection Sort）

• 原理： 每次从未排序的部分中找到最小（或最大）的元素，放到已排序部分的末尾。
• 特点： 实现简单，但效率较低，时间复杂度为 O(n^2)。
• JS实现：

function selectionSort(arr) {
  const 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;
}

// 测试
const arr2 = [5, 2, 8, 1, 9, 4];
console.log("选择排序结果：", selectionSort(arr2)); // 输出：[1, 2, 4, 5, 8, 9]

3. 插入排序（Insertion Sort）

• 原理： 将未排序的元素逐个插入到已排序的部分中，保持已排序部分的有序性。
• 特点： 对于小规模数据或基本有序的数据，效率较高，时间复杂度为 O(n^2)，但平均性能优于冒泡和选择。
• JS实现：

function insertionSort(arr) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    const 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;
}

// 测试
const arr3 = [5, 2, 8, 1, 9, 4];
console.log("插入排序结果：", insertionSort(arr3)); // 输出：[1, 2, 4, 5, 8, 9]

4. 快速排序（Quick Sort）

• 原理： 选择一个基准元素，将数组分成两部分，一部分小于基准，一部分大于基准，然后递归地对两部分进行排序。
• 特点： 平均性能最佳，时间复杂度为 O(n log n)，但最坏情况下为 O(n^2)。
• JS实现：

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const pivot = arr[0];
  const left = [];
  const right = [];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return [...quickSort(left), pivot, ...quickSort(right)];
}

// 测试
const arr4 = [5, 2, 8, 1, 9, 4];
console.log("快速排序结果：", quickSort(arr4)); // 输出：[1, 2, 4, 5, 8, 9]

5. 归并排序（Merge Sort）

• 原理： 将数组递归地分成两部分，分别排序，然后将排序好的两部分合并。
• 特点： 稳定排序，时间复杂度为 O(n log n)。
• JS实现：

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

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

// 测试
const arr5 = [5, 2, 8, 1, 9, 4];
console.log("归并排序结果：", mergeSort(arr5)); // 输出：[1, 2, 4, 5, 8, 9]

三、总结与应用

本文介绍了五种常见的排序算法，并用 JavaScript 进行了实现。每种算法都有其特点和适用场景：

• 冒泡、选择、插入排序： 简单易懂，但效率较低，适用于小规模数据。
• 快速排序： 平均性能最佳，适用于大规模数据，但最坏情况下性能较差。
• 归并排序： 稳定排序，适用于大规模数据，性能稳定。