双向冒泡排序

问题

实现双向冒泡排序（Cocktail Sort），也叫鸡尾酒排序。

解答

双向冒泡排序是普通冒泡排序的改进版。普通冒泡只从左到右单向遍历，而双向冒泡会交替从左到右、从右到左遍历，能更快地将两端的元素归位。

function cocktailSort(arr) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left < right) {
    // 从左到右，把最大值冒泡到右边
    for (let i = left; i < right; i++) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
      }
    }
    right--; // 最大值已归位，右边界左移
    
    // 从右到左，把最小值冒泡到左边
    for (let i = right; i > left; i--) {
      if (arr[i] < arr[i - 1]) {
        [arr[i], arr[i - 1]] = [arr[i - 1], arr[i]];
      }
    }
    left++; // 最小值已归位，左边界右移
  }
  
  return arr;
}

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

优化版本：提前终止

function cocktailSortOptimized(arr) {
  let left = 0;
  let right = arr.length - 1;
  let swapped = true;
  
  while (left < right && swapped) {
    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;
    
    // 从右到左
    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++;
  }
  
  return arr;
}

关键点

• 双向遍历：交替从左到右、从右到左，每轮同时确定最大和最小值的位置
• 边界收缩：每完成一个方向的遍历，对应边界向内收缩
• 提前终止：如果某轮没有发生交换，说明数组已有序，可以提前退出
• 时间复杂度：平均 O(n²)，但对于部分有序的数组比普通冒泡更快
• 空间复杂度：O(1)，原地排序