TypeScript十大排序算法插入排序怎么實現

TypeScript十大排序算法插入排序怎么實現

排序算法是計算機科學中最基礎且重要的算法之一。插入排序（Insertion Sort）是一種簡單直觀的排序算法，它的工作原理類似于我們整理撲克牌的方式。本文將詳細介紹如何在TypeScript中實現插入排序算法，并探討其時間復雜度和適用場景。

1. 插入排序的基本思想

插入排序的基本思想是將一個待排序的數組分為已排序和未排序兩部分。初始時，已排序部分只包含數組的第一個元素，而未排序部分包含剩余的元素。然后，依次將未排序部分的元素插入到已排序部分的適當位置，直到所有元素都被排序。

具體步驟如下：

1. 從第一個元素開始，該元素可以認為已經被排序。
2. 取出下一個元素，在已經排序的元素序列中從后向前掃描。
3. 如果該元素（已排序）大于新元素，將該元素移到下一位置。
4. 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置。
5. 將新元素插入到該位置后。
6. 重復步驟2~5，直到所有元素都被排序。

2. TypeScript實現插入排序

下面是一個使用TypeScript實現插入排序的示例代碼：

function insertionSort(arr: number[]): number[] {
    const n = arr.length;

    for (let i = 1; i < n; i++) {
        const key = arr[i];
        let j = i - 1;

        // 將大于key的元素向后移動
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        // 插入key到正確的位置
        arr[j + 1] = key;
    }

    return arr;
}

// 示例用法
const array = [12, 11, 13, 5, 6];
console.log("排序前:", array);
const sortedArray = insertionSort(array);
console.log("排序后:", sortedArray);

代碼解析

1. 外層循環：for (let i = 1; i < n; i++) 從數組的第二個元素開始遍歷，因為第一個元素默認是已排序的。
2. 內層循環：while (j >= 0 && arr[j] > key) 從當前元素的前一個元素開始向前掃描，找到合適的位置插入當前元素。
3. 插入操作：arr[j + 1] = key 將當前元素插入到正確的位置。

示例輸出

排序前: [12, 11, 13, 5, 6]
排序后: [5, 6, 11, 12, 13]

3. 時間復雜度分析

插入排序的時間復雜度取決于輸入數組的初始狀態：

• 最壞情況：當輸入數組是逆序時，每次插入操作都需要移動所有已排序的元素，時間復雜度為O(n2)。
• 最好情況：當輸入數組已經是有序時，每次插入操作只需要比較一次，時間復雜度為O(n)。
• 平均情況：時間復雜度為O(n2)。

盡管插入排序在最壞情況下的時間復雜度較高，但在處理小規模數據或部分有序的數據時，插入排序的表現往往優于其他復雜度較低的排序算法。

4. 空間復雜度分析

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

5. 插入排序的優缺點

優點

• 簡單直觀：插入排序的實現非常簡單，容易理解和實現。
• 原地排序：不需要額外的存儲空間。
• 穩定排序：相同元素的相對位置不會改變。
• 適用于小規模數據：對于小規模數據或部分有序的數據，插入排序的效率較高。

缺點

• 時間復雜度較高：在最壞情況下，時間復雜度為O(n2)，不適合處理大規模數據。
• 不適合大規模數據：對于大規模數據，插入排序的效率較低，通常選擇更高效的排序算法如快速排序、歸并排序等。

6. 插入排序的適用場景

插入排序適用于以下場景：

• 小規模數據：當數據規模較小時，插入排序的效率較高。
• 部分有序的數據：如果數據已經部分有序，插入排序的效率會顯著提高。
• 在線排序：當數據是逐步到達時，插入排序可以逐步將新數據插入到已排序的部分中。

7. 插入排序的優化

雖然插入排序在最壞情況下的時間復雜度為O(n2)，但可以通過一些優化手段來提高其性能：

7.1 二分查找優化

在插入排序的內層循環中，可以使用二分查找來快速找到插入位置，從而減少比較次數。優化后的時間復雜度為O(n log n)，但由于移動元素的次數仍然為O(n2)，整體時間復雜度仍為O(n2)。

function binaryInsertionSort(arr: number[]): number[] {
    const n = arr.length;

    for (let i = 1; i < n; i++) {
        const key = arr[i];
        let left = 0;
        let right = i - 1;

        // 使用二分查找找到插入位置
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (arr[mid] < key) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        // 將大于key的元素向后移動
        for (let j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }

        // 插入key到正確的位置
        arr[left] = key;
    }

    return arr;
}

// 示例用法
const array = [12, 11, 13, 5, 6];
console.log("排序前:", array);
const sortedArray = binaryInsertionSort(array);
console.log("排序后:", sortedArray);

7.2 希爾排序

希爾排序（Shell Sort）是插入排序的一種改進版本，它通過將數組分成若干個子序列來進行排序，從而減少移動元素的次數。希爾排序的時間復雜度取決于步長序列的選擇，通常為O(n log2 n)。

function shellSort(arr: number[]): number[] {
    const n = arr.length;
    let gap = Math.floor(n / 2);

    while (gap > 0) {
        for (let i = gap; i < n; i++) {
            const temp = arr[i];
            let j = i;

            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }

            arr[j] = temp;
        }

        gap = Math.floor(gap / 2);
    }

    return arr;
}

// 示例用法
const array = [12, 11, 13, 5, 6];
console.log("排序前:", array);
const sortedArray = shellSort(array);
console.log("排序后:", sortedArray);

8. 總結

插入排序是一種簡單且易于實現的排序算法，適用于小規模數據或部分有序的數據。盡管其時間復雜度較高，但在某些特定場景下，插入排序仍然是一個不錯的選擇。通過優化手段如二分查找和希爾排序，可以進一步提高插入排序的性能。

在實際開發中，選擇合適的排序算法需要根據具體的數據規模和特性來決定。對于大規模數據，通常選擇更高效的排序算法如快速排序、歸并排序等；而對于小規模數據或部分有序的數據，插入排序仍然是一個值得考慮的選擇。

希望本文能幫助你更好地理解插入排序的原理和實現，并在實際項目中靈活運用。