JavaScript怎么實現冒泡排序與選擇排序

# JavaScript怎么實現冒泡排序與選擇排序

## 前言

排序算法是計算機科學中最基礎也最重要的概念之一。在JavaScript開發中，理解排序算法的實現原理不僅能幫助我們處理數據排序需求，更能提升對程序性能優化的認知。本文將詳細講解兩種經典排序算法——冒泡排序和選擇排序的JavaScript實現方式，通過代碼示例、性能分析和應用場景對比，幫助開發者深入理解其工作機制。

## 一、冒泡排序算法

### 1. 基本概念
冒泡排序（Bubble Sort）是一種簡單的比較排序算法，它通過重復遍歷待排序列表，比較相鄰元素并交換位置，使較大（或較?。┰刂饾u"浮"到數組末端。

### 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(n2)
  • 平均情況：O(n2)
• 空間復雜度：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(n2)（需要比較n(n-1)/2次）
• 空間復雜度：O(1)（原地排序）

三、兩種算法對比

四、實際應用建議

1. 小規模數據：兩種算法都適用，選擇排序通常交換次數更少
2. 近乎有序數據：優化后的冒泡排序表現更好
3. 現代JavaScript開發：
   • 實際項目中建議使用內置的Array.prototype.sort()
   • V8引擎的sort方法對短數組使用插入排序（O(n2)），對長數組使用TimSort（O(n log n)）

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

五、延伸思考

1. 可視化學習：使用D3.js等庫實現排序過程可視化
2. 性能測試：比較兩種算法在不同規模數據下的實際表現
3. 算法演進：理解從基礎排序到高級排序（如快速排序、歸并排序）的優化思路

結語

雖然冒泡排序和選擇排序在實際項目中很少直接使用，但作為最基礎的排序算法，它們對于理解算法思想、培養編程思維具有重要意義。建議讀者親自動手實現這些算法，并通過調試工具逐步觀察排序過程的變化，這將為學習更復雜的算法打下堅實基礎。 “`

注：本文實際約1800字，完整版可通過擴展每個章節的示例說明、增加可視化圖表或補充更多性能測試數據來達到更精確的字數要求。