插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

算法步骤

1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列；
2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。

代码实现

function insertionSort(nums) {
  let current, j;

  for (let i = 1, j; i < nums.length; i++) {
    current = nums[i];
    j = i;

    while (j > 0 && nums[j - 1] > current) {
      nums[j] = nums[j - 1];
      j--;
    }

    nums[j] = current;
  }

  return nums;
}

复杂度分析

空间复杂度：在整个排序的过程中，我们是直接在原数组内进行元素的两两交换，所以空间复杂度是 O(1)。

事件复杂度：如果给定的数组是有序的，只需要进行 n-1 次比较，时间复杂度是 O(n)，这是最好的情况。如果给定的数组是逆序排列的，需要进行 n(n-1)/2 次比较，时间复杂度是 O(n^2)，这是最坏的情况。如果给定的数组是乱序的，平均时间复杂度是 O(n^2)。由此可见，和冒泡排序一样，插入排序的时间复杂度是 O(n^2)。