插入排序

插入排序

在一个有序的数据序列中，插入一个数，且插入后一样有序，时间复杂度 O(n^2)，适用于少量数据的排序

1. 直接插入排序

• 时间复杂度 O(n^2)
• 思路： 类似抓扑克牌

  3 2 7 4 1 -=> 2 3 7 4 1 -=> 2 3 4 7 1 -=> 1 2 3 4 7

  • 把前面的数当成是有序的,将下一个无序的数字插进有序的数列里。
  • 和 有序数列的最后一个对比，当 插入数 小于 有序数列最后一个，那就插入数再和有序数列倒数第二个比较，(从后往前比较) 直到遇到 插入数 大于 有序数列的那个
  1. 依次比较 前后 2 位 作为 最小有序数列
  2. 当 有序数列 被打破，那么将 打破者 依次与其 前一位(不能小于 0)做比较
  3. 当 打破者 也小于 前一位时，将前一位后移，(即将 j 的前一位的值 赋值给 j )
  4. 当 j == 0 或 由于是有序数列，当 temp > list[j-1] 则表示 temp 在 j 的位置上刚好

function DirectInsertSort(list) {
  let i, j, temp;
  for (i = 1; i < list.length; ++i) {
    temp = list[i];
    j = i - 1;
    while (j >= 0 && temp < list[j]) {
      list[j + 1] = list[j];
      --j;
    }
    list[j + 1] = temp;
  }
}

2. 二分法插入排序

• 时间复杂度 O(n^2)
• 思路：

  和直接插入排序类似，但是将其“依次比较”改为“二分法比较”，减少了比较次数

  1. 获取最小有序数列
  2. 将 打破者 与 前面的有序数列 的 mid 进行比较，根据 打破者 与 当前 mid 的值再修改 low 和 high
  3. 当 low 大于或等于 high 时，则表明 low 的位置即 要插入的位置
  4. 最后循环后移直到 插入位置

function BinaryInsertSort(list) {
  let i, j, high, low, mid, temp;
  for (i = 1; i < list.length; ++i) {
    low = 0;
    high = i - 1;
    temp = list[i];
    while (low <= high) {
      mid = Math.floor((high + low) / 2);
      if (temp < list[mid]) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    for (j = i; j >= low; --j) {
      list[j] = list[j - 1];
    }
    list[low] = temp;
  }
}

3. 希尔插入排序：(也叫缩小增量排序)

• 时间复杂度 O(n^(1.3~2))
• 思路：

  比较一次，但移动一大步，相比直接插入排序，增大了比较次数，但是很大程度减少了交换次数

  1. 本质还是插入排序
  2. 先将整个 数据序列 分割成 若干子序列，分别进行 直接插入排序，待整个序列 基本有序时，再对全体进行一次直接插入排序
  3. 比如先 以 整个数组的一半 为增量，划分几个子序列，排序子序列，之后再以 上一个增量的一半 作为增量，直到最后增量为 1，进行最后一次直接插入排序

function ShellInserSort(list) {
  let i, j, temp;
  let d = Math.floor(list.length / 2);
  while (d > 0) {
    for (i = d; i < list.length; ++i) {
      temp = list[i];
      j = i - d;
      while (j >= 0 && temp < list[j]) {
        list[j + d] = list[j];
        j -= d;
      }
      list[j + d] = temp;
    }
    d = Math.floor(d / 2);
  }
}