排序算法3-插入排序

插入排序

• 平均时间复杂度:O(n^2)
• 最好情况:O(n)
• 最坏情况:O(n^2)
• 空间复杂度:O(1)
• 排序方式:In-place
• 稳定性:稳定

算法步骤:
1.将待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2.从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。
（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

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

改进
优化1 将元素交换改为元素挪动，先记录要插入的值，然后将前面的元素依次往后挪，找到位置了再插入 （交换有三步，挪动就一步）
优化2 插入元素前的序列是有序的，所以插入元素可以采用二分法来找到应插入的位置

//二分法查找插入位置
function findIndex(arr, i) {
  let value = arr[i];
  let begin = 0;
  let end = i;
  while (begin < end) {
    let mid = (begin + end) >> 1; //除2取整
    if (arr[mid] > value) {
      end = mid;
    } else if (arr[mid] < value) {
      if (begin === mid) {
        begin = mid + 1;
      } else {
        begin = mid;
      }
    } else {
      begin = mid + 1;
    }
  }
  return begin;
}

//挪动而非交换
function insertIndexValue(arr, index, i) {
  let temp = arr[i];
  while (index < i) {
    arr[i] = arr[i - 1];
    i--;
  }
  arr[index] = temp;
}

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let index = findIndex(arr, i);
    insertIndexValue(arr, index, i);
  }
}