Published on

插入排序笔记以及实现

Authors
  • avatar
    Name
    Et cetera
    Twitter

介绍插入排序

插入排序是指在待排序的元素中,假设前面 n-1(其中 n>=2)个数已经是排好顺序的,现将第 n 个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第 n 个数的这个序列也是排好顺序的.按照此法对所有元素进行插入,直到整个序列排为有序的过程

实现思路

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

  for (let i = 1; i < n; i++) {
    const num = arr[i];
    let j = i - 1;
    while (arr[j] > num && j >= 0) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = num;
  }

  return arr;
}

时间复杂度:

  • 最好情况: O(n)

  • 最坏情况: O(n^2)

在数列部分有序情况下,插入排序比冒泡排序和选择排序更快;但在完全逆序情况下,不如快速排序、归并排序

View on GitHub