0319.md

插入排序

以第一个元素作为有序数组，其后的元素通过在这个已有序的数组中找到合适的位置并插入。

• 最好： O(n)，原数组已经是升序的。
• 最坏： O(n²)
• 平均： O(n²)

function insertSort(nums) {
  if (!Array.isArray(nums)) {
    return new TypeError('not a array');
  }
  if (nums.length < 2) {
    return nums;
  }

  let len = nums.length;
  for(let i = 0; i < len; i++) {
    let temp = nums[i];
    let j = i;
    while(j >= 0 && temp < nums[j - 1]) {
      nums[j] = nums[j - 1];
      j--;
    }
    nums[j] = temp;
  }
}