插入排序

什么是插入排序

插入排序会维护一个有序区，把元素一个个插入到有序的适当位置，直到所有元素有序为止。

假设有一组无序数组，插入排序会假定数组第一项属于有序区。

接着，它会从第二项开始，与前面的有序区的元素依次比较，根据数字大小在有序区找到合适的位置进行插入。

不断重复上述过程，最终会得到一个排序好的数组。

举个例子，假定待排序数组是[3, 5, 1, 4, 2]。

这些值将被插入排序算法按照下面的步骤进行排序。

1. 假定数组第一项 3 已被排序，属于有序区，所以我们从数组第二个值 5 开始。3 比 5 小，所以 5 待在原位（数组的第二位）。此时，3 和 5 排序完毕，3和5属于有序区。

2. 下一个待排序的值是 1（目前在数组的第三位）。5 比 1 大，所以 5 被 移至第三位去了。继续分析 1 是否应该被插入到第二位——1 比 3 大吗？不，所以 3 被移到第二位去了。因为 0 是第一个位置，所以 1 被插入第一位。1、3、5 三个数字已经排序，1，3和5属于有序区。

3. 然后看下一个值待排序的值是4。4 比 5 小，所以 5 移动到索引 3 位置。4 比 3 大，所 以把 4 插入数组的位置 3 上。 此时，1，3，4，5属于有序区。

4. 最后一个待插入的数字是 2（数组的位置 4）。5 比 2 大，所以 5 移动至索引 4。4 比 2 大， 所以 4 也得移动（位置 3）。3 也比 2 大，所以 3 还得移动。1 比 2 小，所以 2 插入到数组的第二个位置上。此时，1，2，3，4，5属于有序区。至此，数组已排序完成。

下面演示了图形化的插入排序过程:

在排序小型数组时，此算法比选择排序和冒泡排序性能要好。

代码实现

插入排序代码并不复杂，所以实现起来也比较简单。

// 比较用的常量对象(保证代码优雅)
export const Compare = {
  LESS_THAN: -1, // 如果第一个元素小于第二个元素，它就返回-1
  BIGGER_THAN: 1, // 如果第一个元素大于第二个元素，它就返回1
  EQUALS: 0 // 如果元素有相同的引用，它就返回 0
};
// 比较用的方法
export function defaultCompare(a, b) {
  // 如果元素有相同的引用，它就返回 0
  if (a === b) {
    return Compare.EQUALS;
  }
  // 如果第一个元素小于第二个元素，它就返回-1,否之返回1
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
/**
 * 插入排序
 * 插入排序每次排一个数组项，以此方式构建最后的排序数组。
 * @param {array} array 要进行排序的数组
 * @param {function} compareFn // 比较用的方法，默认为defaultCompare
 * @returns {array} 返回排序后的数组
 */
 export const insertionSort = (array, compareFn = defaultCompare) => {
  const { length } = array;  // 声明一个名为length的变量，用来存储数组的长度
  let temp;
  // 主循环 迭代数组来给第 i 项找到正确的位置(假设下标0的元素已经排序好)
  for (let i = 1; i < length; i++) { 
    let j = i; // 用 i 的值来初始化一个辅助变量
    temp = array[i]; // 将其值存储在一个临时变量中(便于之后将其插入到正确的位置上)
    // console.log('to be inserted ' + temp);
    //次循环 找到正确的位置来插入项
    while (j > 0 && compareFn(array[j - 1], temp) === Compare.BIGGER_THAN) { // 只要变量j大于0(因为0下标已被假设排好序)，并且数组前面的值比待比较的值大(也就是如果array[j - 1]比temp大)
      // console.log('shift ' + array[j - 1]);
      array[j] = array[j - 1]; // 我们就把这个值移到当前位置上
      j--; // 并减小 j
    }
    // console.log('insert ' + temp);
    array[j] = temp; // 最终，将该值插入到正确的位置上
  }
  // 返回排序后的数组
  return array;
};