手写冒泡排序

问题

冒泡排序是一种基础的排序算法，通过重复遍历待排序数组，比较相邻元素并交换位置，使较大（或较小）的元素逐渐”冒泡”到数组末尾。请实现一个冒泡排序函数，要求能够正确排序数字数组，并考虑性能优化。

解答

/**
 * 冒泡排序 - 基础版本
 * @param {number[]} arr - 待排序数组
 * @return {number[]} 排序后的数组
 */
function bubbleSort(arr) {
  // 创建副本，避免修改原数组
  const result = [...arr];
  const len = result.length;
  
  // 外层循环控制排序轮数
  for (let i = 0; i < len - 1; i++) {
    // 内层循环进行相邻元素比较和交换
    for (let j = 0; j < len - 1 - i; j++) {
      // 如果前一个元素大于后一个元素，则交换位置
      if (result[j] > result[j + 1]) {
        [result[j], result[j + 1]] = [result[j + 1], result[j]];
      }
    }
  }
  
  return result;
}

/**
 * 冒泡排序 - 优化版本
 * @param {number[]} arr - 待排序数组
 * @return {number[]} 排序后的数组
 */
function bubbleSortOptimized(arr) {
  const result = [...arr];
  const len = result.length;
  
  for (let i = 0; i < len - 1; i++) {
    // 标记本轮是否发生交换
    let swapped = false;
    
    for (let j = 0; j < len - 1 - i; j++) {
      if (result[j] > result[j + 1]) {
        [result[j], result[j + 1]] = [result[j + 1], result[j]];
        swapped = true;
      }
    }
    
    // 如果本轮没有发生交换，说明数组已经有序，提前结束
    if (!swapped) {
      break;
    }
  }
  
  return result;
}

使用示例

// 示例1：基本使用
const arr1 = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(arr1)); 
// 输出: [11, 12, 22, 25, 34, 64, 90]

// 示例2：已排序数组（优化版本性能更好）
const arr2 = [1, 2, 3, 4, 5];
console.log(bubbleSortOptimized(arr2)); 
// 输出: [1, 2, 3, 4, 5]
// 优化版本只需一轮遍历即可结束

// 示例3：包含负数
const arr3 = [3, -1, 4, -5, 2];
console.log(bubbleSort(arr3)); 
// 输出: [-5, -1, 2, 3, 4]

// 示例4：包含重复元素
const arr4 = [5, 2, 8, 2, 9, 1];
console.log(bubbleSort(arr4)); 
// 输出: [1, 2, 2, 5, 8, 9]

// 示例5：空数组和单元素数组
console.log(bubbleSort([])); // 输出: []
console.log(bubbleSort([42])); // 输出: [42]

关键点

• 双层循环结构：外层循环控制排序轮数（n-1轮），内层循环进行相邻元素的比较和交换

• 比较范围优化：每轮排序后，最大元素会”冒泡”到末尾，因此内层循环范围可以减少 i（len - 1 - i）

• 提前终止优化：使用 swapped 标志位，如果某轮遍历没有发生任何交换，说明数组已经有序，可以提前结束排序

• 解构赋值交换：使用 ES6 的解构赋值 [a, b] = [b, a] 简洁地交换两个元素，无需临时变量

• 不修改原数组：通过扩展运算符创建数组副本，保持函数的纯净性

• 时间复杂度：最坏和平均情况为 O(n²)，最好情况（已排序）优化后为 O(n)

• 空间复杂度：O(1)，只需要常数级别的额外空间（不考虑结果数组）

• 稳定性：冒泡排序是稳定排序算法，相等元素的相对位置不会改变