TypeScript怎么實現冒泡排序

TypeScript怎么實現冒泡排序

冒泡排序（Bubble Sort）是一種簡單的排序算法，它通過重復地遍歷要排序的列表，比較相鄰的元素并交換它們的位置，直到整個列表有序為止。盡管冒泡排序的時間復雜度較高（O(n^2)），但由于其實現簡單，常被用于教學和入門級別的算法學習。

本文將詳細介紹如何在TypeScript中實現冒泡排序，并逐步解釋其工作原理。我們將從基本概念開始，逐步深入到代碼實現，最后討論一些優化技巧。

1. 冒泡排序的基本概念

冒泡排序的核心思想是通過不斷地比較相鄰的兩個元素，如果它們的順序錯誤（例如，前一個元素比后一個元素大），就交換它們的位置。這個過程會重復進行，直到沒有任何一對元素需要交換為止。

1.1 冒泡排序的步驟

1. 比較相鄰元素：從列表的第一個元素開始，比較相鄰的兩個元素。
2. 交換元素：如果前一個元素比后一個元素大，交換它們的位置。
3. 重復遍歷：重復上述步驟，直到沒有任何一對元素需要交換。

1.2 冒泡排序的示例

假設我們有一個數組 [5, 3, 8, 4, 6]，冒泡排序的過程如下：

• 第一輪遍歷：

  • 比較 5 和 3，交換位置，數組變為 [3, 5, 8, 4, 6]
  • 比較 5 和 8，不交換
  • 比較 8 和 4，交換位置，數組變為 [3, 5, 4, 8, 6]
  • 比較 8 和 6，交換位置，數組變為 [3, 5, 4, 6, 8]

• 第二輪遍歷：

  • 比較 3 和 5，不交換
  • 比較 5 和 4，交換位置，數組變為 [3, 4, 5, 6, 8]
  • 比較 5 和 6，不交換
  • 比較 6 和 8，不交換

• 第三輪遍歷：

  • 比較 3 和 4，不交換
  • 比較 4 和 5，不交換
  • 比較 5 和 6，不交換
  • 比較 6 和 8，不交換

此時，數組已經有序，排序完成。

2. TypeScript實現冒泡排序

在TypeScript中實現冒泡排序非常簡單。我們可以使用一個嵌套的循環結構來實現這一算法。外層循環控制遍歷的次數，內層循環負責比較和交換相鄰元素。

2.1 基本實現

function bubbleSort(arr: number[]): number[] {
    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]) {
                // 交換 arr[j] 和 arr[j + 1]
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

// 示例用法
const arr = [5, 3, 8, 4, 6];
console.log(bubbleSort(arr)); // 輸出: [3, 4, 5, 6, 8]

2.2 代碼解釋

• 外層循環：for (let i = 0; i < n - 1; i++) 控制遍歷的次數。每次遍歷后，最大的元素會被“冒泡”到數組的末尾，因此內層循環的次數可以減少。

• 內層循環：for (let j = 0; j < n - 1 - i; j++) 負責比較相鄰的元素。n - 1 - i 是因為每次遍歷后，數組末尾的 i 個元素已經有序，不需要再比較。

• 交換元素：如果 arr[j] > arr[j + 1]，則交換這兩個元素的位置。

2.3 優化實現

雖然上述實現已經可以正確排序，但我們可以對其進行一些優化。例如，如果在某次遍歷中沒有發生任何交換，說明數組已經有序，可以提前結束排序。

function bubbleSortOptimized(arr: number[]): number[] {
    const n = arr.length;
    let swapped: boolean;
    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]
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        // 如果沒有發生交換，說明數組已經有序，提前結束
        if (!swapped) {
            break;
        }
    }
    return arr;
}

// 示例用法
const arr = [5, 3, 8, 4, 6];
console.log(bubbleSortOptimized(arr)); // 輸出: [3, 4, 5, 6, 8]

2.4 優化解釋

• swapped 變量：用于記錄在每次遍歷中是否發生了交換。如果在某次遍歷中沒有發生任何交換，說明數組已經有序，可以提前結束排序。

• 提前結束：通過檢查 swapped 變量，可以避免不必要的遍歷，從而提高算法的效率。

3. 冒泡排序的時間復雜度

冒泡排序的時間復雜度為 O(n^2)，其中 n 是數組的長度。這是因為在最壞的情況下，冒泡排序需要進行 n-1 次遍歷，每次遍歷需要比較 n-i 次。

3.1 最好情況

在最好的情況下，數組已經有序，冒泡排序只需要進行一次遍歷即可確定數組有序。此時的時間復雜度為 O(n)。

3.2 最壞情況

在最壞的情況下，數組完全逆序，冒泡排序需要進行 n-1 次遍歷，每次遍歷需要比較 n-i 次。此時的時間復雜度為 O(n^2)。

3.3 平均情況

在平均情況下，冒泡排序的時間復雜度也為 O(n^2)。

4. 冒泡排序的空間復雜度

冒泡排序是一種原地排序算法，它只需要常數級別的額外空間來存儲臨時變量。因此，冒泡排序的空間復雜度為 O(1)。

5. 總結

冒泡排序是一種簡單但效率較低的排序算法，適用于小規模數據的排序。盡管其時間復雜度較高，但由于實現簡單，常被用于教學和入門級別的算法學習。

在TypeScript中實現冒泡排序非常簡單，只需使用嵌套循環結構即可。通過引入 swapped 變量，我們還可以對算法進行優化，提前結束排序過程。

雖然冒泡排序在實際應用中較少使用，但理解其工作原理對于學習更復雜的排序算法（如快速排序、歸并排序等）非常有幫助。希望本文能幫助你更好地理解冒泡排序及其在TypeScript中的實現。