JavaScript怎么实现冒泡排序与选择排序

# JavaScript怎么实现冒泡排序与选择排序

## 前言

排序算法是计算机科学中最基础也最重要的概念之一。在JavaScript开发中，理解排序算法的实现原理不仅能帮助我们处理数据排序需求，更能提升对程序性能优化的认知。本文将详细讲解两种经典排序算法——冒泡排序和选择排序的JavaScript实现方式，通过代码示例、性能分析和应用场景对比，帮助开发者深入理解其工作机制。

## 一、冒泡排序算法

### 1. 基本概念
冒泡排序（Bubble Sort）是一种简单的比较排序算法，它通过重复遍历待排序列表，比较相邻元素并交换位置，使较大（或较小）元素逐渐"浮"到数组末端。

### 2. 算法原理
- 比较相邻元素，如果第一个比第二个大就交换它们
- 对每一对相邻元素做同样工作，从开始到结尾
- 重复上述步骤，每次遍历范围缩小一位（因为末尾已排序）

### 3. JavaScript实现

```javascript
function bubbleSort(arr) {
  const n = arr.length;
  // 外层循环控制遍历轮次
  for (let i = 0; i < n - 1; i++) {
    // 内层循环控制每轮比较次数
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // ES6解构赋值交换元素
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

// 测试示例
const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
console.log("排序前:", unsortedArray);
console.log("排序后:", bubbleSort(unsortedArray));

4. 优化版本

通过添加标志位可提前终止已排序数组的无效遍历：

function optimizedBubbleSort(arr) {
  const n = arr.length;
  let swapped;
  for (let i = 0; i < n - 1; i++) {
    swapped = false;
    for (let j = 0; j < n - 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;
}

5. 复杂度分析

• 时间复杂度：
  • 最优情况（已排序）：O(n)
  • 最差情况（逆序）：O(n²)
  • 平均情况：O(n²)
• 空间复杂度：O(1)（原地排序）

二、选择排序算法

1. 基本概念

选择排序（Selection Sort）通过不断选择剩余元素中的最小值（或最大值）放到已排序序列的末尾。

2. 算法原理

• 在未排序序列中找到最小元素
• 将其与未排序序列的第一个元素交换
• 重复上述过程直到所有元素排序完成

3. JavaScript实现

function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    // 假设当前i为最小值索引
    let minIndex = i;
    // 在未排序部分查找最小值
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // 将最小值交换到已排序序列末尾
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  return arr;
}

// 测试示例
const unsortedArray2 = [29, 10, 14, 37, 13];
console.log("排序前:", unsortedArray2);
console.log("排序后:", selectionSort(unsortedArray2));

4. 双向选择排序优化

可以同时查找最小和最大值来减少遍历次数：

function bidirectionalSelectionSort(arr) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    let minIndex = left, maxIndex = right;
    
    // 确保min <= max
    if (arr[minIndex] > arr[maxIndex]) {
      [arr[minIndex], arr[maxIndex]] = [arr[maxIndex], arr[minIndex]];
    }
    
    // 在中间区间查找极值
    for (let i = left + 1; i < right; i++) {
      if (arr[i] < arr[minIndex]) {
        minIndex = i;
      } else if (arr[i] > arr[maxIndex]) {
        maxIndex = i;
      }
    }
    
    // 交换最小值
    [arr[left], arr[minIndex]] = [arr[minIndex], arr[left]];
    // 交换最大值
    [arr[right], arr[maxIndex]] = [arr[maxIndex], arr[right]];
    
    left++;
    right--;
  }
  return arr;
}

5. 复杂度分析

• 时间复杂度：
  • 所有情况：O(n²)（需要比较n(n-1)/2次）
• 空间复杂度：O(1)（原地排序）

三、两种算法对比

四、实际应用建议

1. 小规模数据：两种算法都适用，选择排序通常交换次数更少
2. 近乎有序数据：优化后的冒泡排序表现更好
3. 现代JavaScript开发：
   • 实际项目中建议使用内置的Array.prototype.sort()
   • V8引擎的sort方法对短数组使用插入排序（O(n²)），对长数组使用TimSort（O(n log n)）

// 现代JS推荐做法
const sortedArray = [...unsortedArray].sort((a, b) => a - b);

五、延伸思考

1. 可视化学习：使用D3.js等库实现排序过程可视化
2. 性能测试：比较两种算法在不同规模数据下的实际表现
3. 算法演进：理解从基础排序到高级排序（如快速排序、归并排序）的优化思路

结语

虽然冒泡排序和选择排序在实际项目中很少直接使用，但作为最基础的排序算法，它们对于理解算法思想、培养编程思维具有重要意义。建议读者亲自动手实现这些算法，并通过调试工具逐步观察排序过程的变化，这将为学习更复杂的算法打下坚实基础。 “`

注：本文实际约1800字，完整版可通过扩展每个章节的示例说明、增加可视化图表或补充更多性能测试数据来达到更精确的字数要求。