Bubble 排序 Algorithm
你将构建什么
`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
设置外部循环
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
添加内部 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
测试使用 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
添加 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
添加输入验证
在主逻辑入口处添加输入验证:检查输入是否为有效数字、是否在允许范围内,对非法输入给出清晰提示而非崩溃。这是健壮程序的第一道防线。
代码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);预期结果
非法输入(非数字或超出范围)会抛出清晰的错误信息,合法输入正常通过。
提示
使用 try/catch 包裹调用处,向用户展示友好的错误提示。
自己动手试试
function bubbleSort(arr) {
// TODO: implement bubble sort with snapshots
return { sorted: arr, snapshots: [arr] };
}function bubbleSort(arr) {
const a = [...arr];
const snapshots = [[...a]];
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;
}
return { sorted: a, snapshots };
}
const result = bubbleSort([5, 3, 8, 1, 2]);
console.log('Sorted:', result.sorted);你学到了什么
你 implemented classic 排序 algorithm 使用 nested 循环, 学习到 track algorithm 状态通过 snapshots, and 添加 optimization (early exit) — skills 那个 transfer 到理解任何 comparison-based algorithm.
相关资源
相关练习
- Predict for 循环输出
练习 tracing 循环 execution.
查阅不认识的术语
新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。