位置：首页-资讯-前端开发

TypeScript十大排序算法插入排序实现示例详解

2023-02-23 11:31

短信预约 -IT技能 免费直播动态提醒

一. 插入排序的定义

插入排序就像是你打扑克牌，你从牌堆顶取一张牌，找到合适的位置插入到已有牌的顺序中，并不断重复这一步骤直到所有的牌都被插入到合适的位置，最终使得整副牌有序。

与打牌类似，插入排序（Insertion sort）的实现方法是：

首先假设第一个数据是已经排好序的，接着取出下一个数据，在已经排好序的数据中从后往前扫描，找到比它小的数的位置，将该位置之后的数整体后移一个单位，然后再将该数插入到该位置。
不断重复上述操作，直到所有的数据都插入到已经排好序的数据中，排序完成。

插入排序的优势在于它的性能表现在已经有序的序列上比冒泡排序、选择排序两种算法要好。

它的时间复杂度为O(n)，因此，如果序列已经被排好，插入排序将会比冒泡排序和选择排序快得多。
另外，插入排序空间复杂度为O(1)，因此，对于内存限制较小的情况，插入排序也是一个更优的选择。

二. 插入排序的流程

插入排序的流程如下：

首先，假设数组的第一个元素已经排好序了，因为它只有一个元素，所以可以认为是有序的。
然后，从第二个元素开始，不断与前面的有序数组元素进行比较。
如果当前元素小于前面的有序数组元素，则把当前元素插入到前面的合适位置。
否则，继续与前面的有序数组元素进行比较。
以此类推，直到整个数组都有序。
循环步骤2~5，直到最后一个元素。
完成排序。

三. 插入排序的图解

四. 插入排序的代码

以下是 TypeScript 实现的插入排序代码，带有详细的注释：

function insertionSort(arr: number[]): number[] {
  // 对于数组的每一个元素，从它开始到0位置，比较该元素和前一个元素的大小
  for (let i = 1; i < arr.length; i++) {
    let current = arr[i];
    let j = i - 1;
    // 如果该元素小于前一个元素，那么前一个元素向后移动，并继续向前比较
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    // 如果该元素大于前一个元素，那么它将放到合适的位置
    arr[j + 1] = current;
  }
  // 返回排序后的数组
  return arr;
}
// 测试数据
const testArr = [5, 2, 9, 1, 5, 6];
// 调用插入排序函数
const sortedArr = insertionSort(testArr);
// 打印结果
console.log(sortedArr);

代码执行的过程：

首先我们定义了一个 insertSort 函数，并传入一个数字数组作为参数。
接着我们定义一个变量 current，它将存储当前需要比较的数字。
然后我们使用一个循环，将数组的第二项到最后一项依次与前面的数字进行比较。
在内层循环中，我们首先将 j 定义为 i-1，然后每次执行循环时，如果 j 大于等于 0 并且 arr[j] 大于 current，我们就交换 arr[j] 和 arr[j + 1] 的值。
在循环结束后，我们将 current 插入到正确的位置，并继续比较下一个数字。
当所有数字都被比较过后，我们就可以返回最终排序好的数组。