# 插入排序

插入排序有两个循环。外循环将数组元素挨个移动，而内循环则对外循环中选中的元素及它后面的那个元素进行比较。如果外循环中选中的元素比内循环中选中的元素小，那么数组元素会向右移动，为内循环中的这个元素腾出位置。

# 算法逻辑

具体实现过程如下(（假设需要排序的数据存在一个数组变量array里面，左往右，从小到大排序):

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

# 代码实现

function insertOrder(array) {
  var len = array.length;

  for (var i = 1; i < len; i++) {
    var temp = array[i],
      j = i;

    while (j > 0 && array[j - 1] > temp) {
      array[j] = array[j - 1];
      j--;
    }

    array[j] = temp;
  }

  return array;
}

# 总结

插入排序的时间复杂度为O(n^2),算法稳定。

TIP

算法视频演示 (opens new window)

← 选择排序