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(n²)。
• 最好情况：当输入数组已经是有序时，每次插入操作只需要比较一次，时间复杂度为O(n)。
• 平均情况：时间复杂度为O(n²)。

尽管插入排序在最坏情况下的时间复杂度较高，但在处理小规模数据或部分有序的数据时，插入排序的表现往往优于其他复杂度较低的排序算法。

4. 空间复杂度分析

插入排序是一种原地排序算法，它只需要常数级别的额外空间来存储临时变量，因此空间复杂度为O(1)。

5. 插入排序的优缺点

优点

• 简单直观：插入排序的实现非常简单，容易理解和实现。
• 原地排序：不需要额外的存储空间。
• 稳定排序：相同元素的相对位置不会改变。
• 适用于小规模数据：对于小规模数据或部分有序的数据，插入排序的效率较高。

缺点

• 时间复杂度较高：在最坏情况下，时间复杂度为O(n²)，不适合处理大规模数据。
• 不适合大规模数据：对于大规模数据，插入排序的效率较低，通常选择更高效的排序算法如快速排序、归并排序等。

6. 插入排序的适用场景

插入排序适用于以下场景：

• 小规模数据：当数据规模较小时，插入排序的效率较高。
• 部分有序的数据：如果数据已经部分有序，插入排序的效率会显著提高。
• 在线排序：当数据是逐步到达时，插入排序可以逐步将新数据插入到已排序的部分中。

7. 插入排序的优化

虽然插入排序在最坏情况下的时间复杂度为O(n²)，但可以通过一些优化手段来提高其性能：

7.1 二分查找优化

在插入排序的内层循环中，可以使用二分查找来快速找到插入位置，从而减少比较次数。优化后的时间复杂度为O(n log n)，但由于移动元素的次数仍然为O(n²)，整体时间复杂度仍为O(n²)。

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 log² 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. 总结

插入排序是一种简单且易于实现的排序算法，适用于小规模数据或部分有序的数据。尽管其时间复杂度较高，但在某些特定场景下，插入排序仍然是一个不错的选择。通过优化手段如二分查找和希尔排序，可以进一步提高插入排序的性能。

在实际开发中，选择合适的排序算法需要根据具体的数据规模和特性来决定。对于大规模数据，通常选择更高效的排序算法如快速排序、归并排序等；而对于小规模数据或部分有序的数据，插入排序仍然是一个值得考虑的选择。

希望本文能帮助你更好地理解插入排序的原理和实现，并在实际项目中灵活运用。