Skip to content

Bubble 排序 Algorithm

中等 约 30 分钟

你将构建什么

`bubbleSort(arr)` 函数那个排序数组的 数字 in ascending 顺序 and 返回数组的 snapshots showing 数组之后每个通过.

学习目标

  • Implement classic 排序 algorithm
  • Use nested 循环到 compare and swap 元素
  • Track algorithm's progress 通过 snapshots
  • 理解为什么 bubble 排序是 O(n²)

前置要求

  • 数组 and 数组 indexing
  • Nested for 循环
  • 变量 swapping 使用 temp 变量

步骤

  1. 1

    设置外部循环

    Bubble 排序制作多个通过通过数组. 每个通过 moves largest unsorted 元素到 它的正确位置. 外部循环 controls 数字的 通过.

    代码
    function bubbleSort(arr) {
      const a = [...arr]; // copy to avoid mutation
      const snapshots = [[...a]];
      for (let i = 0; i < a.length - 1; i++) {
        // inner loop comes next
      }
      return { sorted: a, snapshots };
    }

    预期结果

    函数 skeleton 是 ready 使用复制的 输入数组.

  2. 2

    添加内部 comparison 循环

    内部外部循环, compare adjacent 元素 and swap 它们如果它们是 in 错误顺序. 之后每个通过, take snapshot 的数组状态.

    代码
        for (let j = 0; j < a.length - 1 - i; j++) {
          if (a[j] > a[j + 1]) {
            const temp = a[j];
            a[j] = a[j + 1];
            a[j + 1] = temp;
          }
        }
        snapshots.push([...a]);

    预期结果

    每个通过 swaps adjacent out-的-顺序元素, bubbling larger 值到 正确.

  3. 3

    测试使用 unsorted 数组

    Call 函数使用 unsorted 数组 and inspect 两者都排序 result and snapshots 到 see 如何数组 evolves.

    代码
    const result = bubbleSort([5, 3, 8, 1, 2]);
    console.log('Sorted:', result.sorted);
    console.log('Passes:', result.snapshots.length);
    result.snapshots.forEach((snap, i) => console.log(`Pass ${i}:`, snap));

    预期结果

    排序: [1, 2, 3, 5, 8] 使用 snapshots showing 每个中级状态.

  4. 4

    添加 optimization

    添加 flag 到 detect 如果任何 swaps 是制作 in 通过. 如果否 swaps occurred, 数组是 already 排序 and 我们能 exit early.

    代码
      for (let i = 0; i < a.length - 1; i++) {
        let swapped = false;
        for (let j = 0; j < a.length - 1 - i; j++) {
          if (a[j] > a[j + 1]) {
            [a[j], a[j + 1]] = [a[j + 1], a[j]];
            swapped = true;
          }
        }
        snapshots.push([...a]);
        if (!swapped) break; // early exit
      }

    预期结果

    Nearly-排序数组 finish in fewer 通过 thanks 到 early exit.

  5. 5

    添加输入验证

    在主逻辑入口处添加输入验证:检查输入是否为有效数字、是否在允许范围内,对非法输入给出清晰提示而非崩溃。这是健壮程序的第一道防线。

    代码
    function validateInput(value, min, max) {
      if (typeof value !== "number" || Number.isNaN(value)) {
        throw new Error(`Invalid input: ${value} is not a number`);
      }
      if (value < min || value > max) {
        throw new Error(`Input ${value} out of range [${min}, ${max}]`);
      }
      return value;
    }
    
    // Usage
    const input = validateInput(rawInput, 1, 100);

    预期结果

    非法输入(非数字或超出范围)会抛出清晰的错误信息,合法输入正常通过。

自己动手试试

你学到了什么

你 implemented classic 排序 algorithm 使用 nested 循环, 学习到 track algorithm 状态通过 snapshots, and 添加 optimization (early exit) — skills 那个 transfer 到理解任何 comparison-based algorithm.

相关资源

相关课程

  • 循环

    Nested 循环 drive comparison 通过.

  • 数组

    数组 indexing and swapping 是核心到 algorithm.

相关练习

查阅不认识的术语

新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。

查看术语表

解读错误信息

用大白话解释常见错误——什么意思、为什么发生、如何修复。

查看错误

← 返回主题