单向冒泡排序

问题

实现单向冒泡排序算法，将数组按升序排列。

解答

function bubbleSort(arr) {
  const len = arr.length;
  
  // 外层循环：控制排序轮数
  for (let i = 0; i < len - 1; i++) {
    // 内层循环：每轮将最大值冒泡到末尾
    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]];
      }
    }
  }
  
  return arr;
}

// 测试
console.log(bubbleSort([5, 3, 8, 4, 2])); // [2, 3, 4, 5, 8]
console.log(bubbleSort([1, 2, 3, 4, 5])); // [1, 2, 3, 4, 5]

优化版本：提前退出

function bubbleSortOptimized(arr) {
  const len = arr.length;
  
  for (let i = 0; i < len - 1; i++) {
    let 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;
}

// 测试：对于已排序数组，只需一轮遍历
console.log(bubbleSortOptimized([1, 2, 3, 4, 5])); // [1, 2, 3, 4, 5]

关键点

• 外层循环控制轮数，共需 n-1 轮
• 内层循环范围逐轮缩小，因为每轮末尾元素已就位
• 相邻元素两两比较，大的往后移动
• 优化：若某轮无交换，数组已有序，可提前退出
• 时间复杂度：O(n²)，空间复杂度：O(1)