TypeScript怎么實現歸并排序

TypeScript怎么實現歸并排序

歸并排序（Merge Sort）是一種經典的排序算法，采用分治法（Divide and Conquer）的思想。它將數組分成兩個子數組，分別對子數組進行排序，然后將排序后的子數組合并成一個有序的數組。歸并排序的時間復雜度為O(n log n)，是一種穩定的排序算法。

本文將詳細介紹如何使用TypeScript實現歸并排序，并逐步解釋算法的實現細節。

1. 歸并排序的基本思想

歸并排序的核心思想是“分而治之”。具體步驟如下：

1. 分割（Divide）：將數組從中間分成兩個子數組，遞歸地對子數組進行分割，直到每個子數組只包含一個元素。
2. 合并（Merge）：將兩個有序的子數組合并成一個有序的數組。

歸并排序的關鍵在于合并操作。合并時，我們需要比較兩個子數組的元素，并按順序將它們放入一個新的數組中。

2. TypeScript實現歸并排序

下面是一個完整的TypeScript實現歸并排序的代碼示例：

function mergeSort(arr: number[]): number[] {
    // 如果數組長度小于等于1，直接返回
    if (arr.length <= 1) {
        return arr;
    }

    // 找到數組的中間位置
    const middle = Math.floor(arr.length / 2);

    // 分割數組為左右兩部分
    const left = arr.slice(0, middle);
    const right = arr.slice(middle);

    // 遞歸地對左右兩部分進行排序
    const sortedLeft = mergeSort(left);
    const sortedRight = mergeSort(right);

    // 合并兩個有序數組
    return merge(sortedLeft, sortedRight);
}

function merge(left: number[], right: number[]): number[] {
    let result: number[] = [];
    let leftIndex = 0;
    let rightIndex = 0;

    // 比較左右兩個數組的元素，按順序放入結果數組
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }

    // 將剩余的元素放入結果數組
    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// 測試代碼
const arr = [38, 27, 43, 3, 9, 82, 10];
const sortedArr = mergeSort(arr);
console.log(sortedArr); // 輸出: [3, 9, 10, 27, 38, 43, 82]

3. 代碼解析

3.1 mergeSort 函數

mergeSort 函數是歸并排序的主函數。它的作用是將數組分割成兩個子數組，并遞歸地對子數組進行排序。

function mergeSort(arr: number[]): number[] {
    if (arr.length <= 1) {
        return arr;
    }

    const middle = Math.floor(arr.length / 2);
    const left = arr.slice(0, middle);
    const right = arr.slice(middle);

    const sortedLeft = mergeSort(left);
    const sortedRight = mergeSort(right);

    return merge(sortedLeft, sortedRight);
}

• 遞歸終止條件：如果數組的長度小于等于1，說明數組已經是有序的，直接返回。
• 分割數組：通過 Math.floor(arr.length / 2) 找到數組的中間位置，并使用 slice 方法將數組分成左右兩部分。
• 遞歸調用：對左右兩部分分別調用 mergeSort 函數進行排序。
• 合并結果：調用 merge 函數將兩個有序的子數組合并成一個有序的數組。

3.2 merge 函數

merge 函數的作用是將兩個有序的數組合并成一個有序的數組。

function merge(left: number[], right: number[]): number[] {
    let result: number[] = [];
    let leftIndex = 0;
    let rightIndex = 0;

    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }

    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

• 初始化指針：leftIndex 和 rightIndex 分別指向左右兩個數組的起始位置。
• 比較元素：比較左右兩個數組當前指針位置的元素，將較小的元素放入結果數組，并移動相應的指針。
• 處理剩余元素：如果其中一個數組的元素已經全部放入結果數組，將另一個數組的剩余元素直接放入結果數組。

4. 歸并排序的時間復雜度

歸并排序的時間復雜度為O(n log n)，其中：

• 分割操作：每次將數組分成兩半，時間復雜度為O(log n)。
• 合并操作：每次合并兩個有序數組，時間復雜度為O(n)。

由于歸并排序的時間復雜度較低，因此它適用于大規模數據的排序。

5. 歸并排序的空間復雜度

歸并排序的空間復雜度為O(n)，因為合并操作需要額外的空間來存儲結果數組。

6. 歸并排序的穩定性

歸并排序是一種穩定的排序算法。在合并過程中，如果兩個元素相等，優先選擇左邊的元素，因此不會改變相等元素的相對順序。

7. 歸并排序的優化

雖然歸并排序的時間復雜度較低，但在實際應用中，我們可以通過以下方式對其進行優化：

7.1 小數組使用插入排序

對于小規模的數組，插入排序的性能可能優于歸并排序。因此，可以在遞歸的終止條件中，當數組長度小于某個閾值時，使用插入排序。

function mergeSort(arr: number[]): number[] {
    if (arr.length <= 16) {
        return insertionSort(arr);
    }

    const middle = Math.floor(arr.length / 2);
    const left = arr.slice(0, middle);
    const right = arr.slice(middle);

    const sortedLeft = mergeSort(left);
    const sortedRight = mergeSort(right);

    return merge(sortedLeft, sortedRight);
}

function insertionSort(arr: number[]): number[] {
    for (let i = 1; i < arr.length; i++) {
        const key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

7.2 避免頻繁創建新數組

在合并操作中，可以通過傳遞索引參數來避免頻繁創建新數組，從而減少內存開銷。

8. 總結

歸并排序是一種高效且穩定的排序算法，適用于大規模數據的排序。通過TypeScript實現歸并排序，我們可以清晰地理解其分治思想和合并操作。在實際應用中，可以通過優化手段進一步提升歸并排序的性能。

希望本文對你理解歸并排序及其TypeScript實現有所幫助！如果你有任何問題或建議，歡迎留言討論。