解题思路 or 实现原理

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列, 对于未排序数据, 在已排序序列中从后向前扫描, 找到相应位置并插入。

算法步骤

n 个记录的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。具体算法描述如下:

• 从第一个元素开始, 该元素可以认为已经被排序;
• 取出下一个元素, 在已经排序的元素序列中从后向前扫描;
• 如果该元素（已排序）大于新元素, 将该元素移到下一位置;
• 重复步骤3, 直到找到已排序的元素小于或者等于新元素的位置;
• 将新元素插入到该位置后;
• 重复步骤 2~5。

实现代码

/*
 * @Author: Rainy
 * @Date: 2019-11-14 19:25:01
 * @LastEditors: Rainy
 * @LastEditTime: 2019-11-24 21:02:34
 */

import { BaseArrayMap } from 'types';

export function insertionSort(arr: BaseArrayMap): BaseArrayMap {
  let len = arr.length;
  if (len < 2) {
    return arr;
  }
  let preIndex: number = 0;
  let current: any = null;
  for (let i = 1; i < len; i++) {
    preIndex = i - 1;
    current = arr[i];
    while (preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex + 1] = arr[preIndex];
      preIndex--;
    }
    arr[preIndex + 1] = current;
  }
  return arr;
}

参考

insertionSort (opens new window)