【JavaScript 算法】冒泡排序：简单有效的排序方法

冒泡排序（Bubble Sort）是一种基础的排序算法，通过重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就交换它们的位置，直到整个数列有序。虽然冒泡排序的效率不高，但其实现简单，适用于小规模数据的排序。本文将详细介绍冒泡排序算法的原理、实现及其应用。

一、算法原理

冒泡排序通过相邻元素的比较和交换，使较大的元素逐渐“冒泡”到数列的末尾。其基本步骤如下：

1. 从数列的起始位置开始，依次比较相邻的两个元素。
2. 如果前一个元素大于后一个元素，则交换它们的位置。
3. 继续遍历数列，重复上述步骤，直到数列末尾。
4. 每一轮遍历后，数列中最大的元素会被移动到正确的位置。
5. 重复步骤1-4，忽略已经排好序的部分，直到整个数列有序。

二、算法实现

以下是冒泡排序的JavaScript实现：

/**
 * 冒泡排序算法
 * @param {number[]} arr - 需要排序的数组
 * @return {number[]} - 排序后的数组
 */
function bubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len; 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;
}

// 示例
const arr = [5, 2, 9, 1, 5, 6];
const sortedArr = bubbleSort(arr);
console.log(sortedArr); // 输出: [1, 2, 5, 5, 6, 9]

三、应用场景

1. 小规模数据排序：冒泡排序适用于小规模数据的排序，因其实现简单。
2. 教学演示：作为一种基础排序算法，冒泡排序常用于教学和演示算法思想。
3. 部分有序数据：如果数据几乎有序，冒泡排序可以很快完成排序。

四、优化与扩展

1. 优化冒泡排序：通过设置一个标志位，可以提前终止排序过程，从而提高效率。

/**
 * 优化冒泡排序算法
 * @param {number[]} arr - 需要排序的数组
 * @return {number[]} - 排序后的数组
 */
function optimizedBubbleSort(arr) {
  const len = arr.length;
  let swapped;
  for (let i = 0; i < len; i++) {
    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;
}

// 示例
const optimizedArr = optimizedBubbleSort(arr);
console.log(optimizedArr); // 输出: [1, 2, 5, 5, 6, 9]

2. 双向冒泡排序：也称鸡尾酒排序，通过从两端向中间排序，进一步优化性能。

/**
 * 双向冒泡排序算法（鸡尾酒排序）
 * 该算法通过从两端向中间排序，进一步优化冒泡排序的性能。
 * @param {number[]} arr - 需要排序的数组
 * @return {number[]} - 排序后的数组
 */
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; // 返回排序后的数组
}

// 示例
const arr = [5, 2, 9, 1, 5, 6];
const cocktailSortedArr = cocktailSort(arr);
console.log(cocktailSortedArr); // 输出: [1, 2, 5, 5, 6, 9]

五、总结

冒泡排序是一种简单直观的排序算法，通过相邻元素的比较和交换，使数据逐渐有序。虽然其效率较低，但通过优化和扩展，可以在某些场景下提高性能。理解和掌握冒泡排序有助于学习和理解更复杂的排序算法。