JavaScript 基础算法：实现列表排序

为什么需要学习手写排序算法

虽然 Array.prototype.sort() 提供了便捷的排序功能，但在面试、性能瓶颈排查或自定义比较逻辑时，手动实现算法能提供更深的理解。掌握这些基础有助于判断不同场景下最适合的排序策略，避免不当使用导致的性能问题。

准备条件与环境配置

无需安装任何额外依赖，所有代码均可直接在浏览器控制台（F12）或 Node.js 环境中运行。建议准备一个文本编辑器用于编写示例代码，并开启浏览器的开发者工具查看执行结果。

核心算法实现步骤

第 1 步：实现冒泡排序（Bubble Sort）

目的： 通过重复遍历要排序的列表，比较相邻元素并交换顺序，直到没有需要交换的元素为止。适合理解基础的嵌套循环逻辑。

代码实现：

function bubbleSort(arr) {
  const len = arr.length;
  let swapped;
  // 外层循环控制比较轮数
  for (let i = 0; i < len - 1; i++) {
    swapped = false;
    // 内层循环进行相邻元素比较
    for (let j = 0; j < len - 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;
}

完成状态： 调用 bubbleSort([5, 2, 9, 1]) 后，返回 [1, 2, 5, 9]。该算法时间复杂度为 O(n²)，适用于小规模数据集。

第 2 步：实现快速排序（Quick Sort）

目的： 采用分治法思想，选取基准值将数组分为两部分，递归排序。这是实际开发中最常用的高效排序算法之一，平均时间复杂度为 O(n log n)。

代码实现：

function quickSort(arr) {
  // 基准情况：数组长度小于等于 1 时直接返回
  if (arr.length <= 1) return arr;
  
  const pivotIndex = Math.floor(arr.length / 2);
  // 选取基准元素（中间值）
  const pivot = arr.splice(pivotIndex, 1)[0];
  
  const left = [];
  const right = [];
  
  // 遍历剩余元素，小于基准放入左边，大于放入右边
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  
  // 递归连接左右数组
  return [...quickSort(left), pivot, ...quickSort(right)];
}

完成状态： 调用 quickSort([38, 27, 43, 3, 9]) 返回 [3, 9, 27, 38, 43]。注意此实现会创建新数组，若需原地排序需调整写法。

验证与测试

可以通过以下通用测试函数验证算法正确性：

function testSort(sortFunc, testArr, expectedArr) {
  const result = sortFunc([...testArr]); // 传入副本以免修改原数组
  const isCorrect = JSON.stringify(result) === JSON.stringify(expectedArr);
  console.log(`测试 ${sortFunc.name}: ${isCorrect ? '通过' : '失败'}`);
  if (!isCorrect) console.log('期望:', expectedArr, '得到:', result);
}

testSort(bubbleSort, [5, 1, 4, 2, 8], [1, 2, 4, 5, 8]);
testSort(quickSort, [10, 0, 3, 9, 2], [0, 2, 3, 9, 10]);

常见问题排错

• 栈溢出错误： 在使用递归排序（如快速排序）处理超大数据集时，可能导致调用栈深度超限。解决方案是改用迭代方式或增加堆大小限制。
• 引用类型问题： 如果数组包含对象而非基本类型，默认比较可能无效。需要在算法中加入自定义比较器参数，例如 (a, b) => a.value - b.value。

简要总结

通过手工实现冒泡和快速排序，我们不仅掌握了 JavaScript 循环与递归的高级用法，也理解了算法效率对程序性能的影响。在实际工程中，应根据数据量级和业务需求选择合适的排序策略。以上就是 JavaScript 算法学习实现代码的详细内容，更多关于 JavaScript 高级技巧的资料请关注本站其它相关文章！