冒泡排序的基本原理与JavaScript实现
冒泡排序是一种简单的排序算法,其核心思想是通过多次遍历待排序序列，每次比较相邻的两个元素，如果它们的顺序错误（例如前一个元素大于后一个元素），就交换它们的位置，这样，每一轮遍历都会将当前未排序部分的最大元素“冒泡”到序列的末尾，就像水中的气泡逐渐上浮一样。
基础代码实现
以下是冒泡排序的JavaScript基础实现：
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 交换元素
}
}
}
return arr;
}
这段代码通过两层循环实现排序,外层循环控制遍历轮数，内层循环负责比较相邻元素并交换位置，时间复杂度为O(n²)，适用于小规模数据排序，但在处理大数据量时效率较低。
优化冒泡排序的必要性
基础版本的冒泡排序存在明显的性能问题：即使数组已经有序，算法仍会执行完整的n-1轮遍历，导致不必要的计算，对已排序数组[1, 2, 3, 4, 5]进行排序时，基础算法仍会执行10次比较（n=5时），每次遍历后，最大的元素已经就位，但内层循环仍会重复比较这些已排序的元素，浪费计算资源。
优化策略一：提前终止排序
通过引入一个标志位swapped，记录每轮遍历中是否发生交换，如果某一轮遍历未发生任何交换，说明数组已经有序，可以提前终止排序，优化后的代码如下：
function optimizedBubbleSort1(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let swapped = false;
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}
if (!swapped) break; // 提前终止
}
return arr;
}
此优化将最好情况（已排序数组）的时间复杂度从O(n²)降至O(n)，仅需一轮遍历即可完成排序。
优化策略二：记录最后一次交换的位置
在每一轮遍历中,最后一次交换的位置之后的元素已经有序，下一轮遍历无需比较这些元素，可以将内层循环的边界优化为最后一次交换的位置，代码实现如下：
function optimizedBubbleSort2(arr) {
const n = arr.length;
let lastSwapIndex = n - 1;
for (let i = 0; i < n - 1; i++) {
let swapped = false;
let currentSwapIndex = 0;
for (let j = 0; j < lastSwapIndex; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
currentSwapIndex = j; // 记录最后一次交换的位置
}
}
lastSwapIndex = currentSwapIndex; // 更新下一轮遍历的边界
if (!swapped) break;
}
return arr;
}
此优化进一步减少了内层循环的比较次数,对数组[3, 1, 2, 4, 5, 6]排序时，第一轮遍历后，4、5、6已就位，下一轮遍历只需比较到2的位置。
优化策略三：双向冒泡排序（鸡尾酒排序）
传统冒泡排序每次仅将最大元素冒泡到末尾,而双向冒泡排序（鸡尾酒排序）通过交替从左到右和从右到左的遍历，同时将最大元素冒泡到末尾、最小元素冒泡到开头，减少遍历轮数，代码实现如下：
function cocktailBubbleSort(arr) {
const n = arr.length;
let left = 0;
let right = n - 1;
while (left < right) {
let swapped = false;
// 从左到右冒泡最大元素
for (let i = left; i < right; i++) {
if (arr[i] > arr[i + 1]) {
[arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
swapped = true;
}
}
right--; // 缩右边界
if (!swapped) break;
swapped = false;
// 从右到左冒泡最小元素
for (let i = right; i > left; i--) {
if (arr[i] < arr[i - 1]) {
[arr[i], arr[i - 1]] = [arr[i - 1], arr[i]];
swapped = true;
}
}
left++; // 缩左边界
if (!swapped) break;
}
return arr;
}
双向冒泡排序适用于元素大部分有序的场景,例如[2, 3, 4, 5, 1]，仅需两轮遍历即可完成排序。
性能对比与适用场景
| 优化策略 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 适用场景 |
|---|---|---|---|---|
| 基础冒泡排序 | O(n²) | O(n²) | O(n²) | 小规模数据或教学演示 |
| 提前终止 | O(n) | O(n²) | O(n²) | 部分有序数据 |
| 记录交换位置 | O(n) | O(n²) | O(n²) | 数据分布不均匀的场景 |
| 双向冒泡排序 | O(n) | O(n²) | O(n²) | 大部分有序的数据 |
冒泡排序虽然简单,但通过优化可以显著提升性能，提前终止、记录交换位置和双向冒泡排序等策略，能有效减少不必要的比较和交换操作，在实际开发中，如果数据规模较小或基本有序，优化后的冒泡排序仍是一个可行的选择；但对于大规模数据，建议采用更高效的排序算法（如快速排序或归并排序），理解这些优化思路不仅有助于掌握算法设计技巧，还能为解决实际问题提供更多思路。
