插入排序

分析

将序列分为两个部分，一部分是有序的，一部分是无序的，现在要做的是，就是不断的从无序的部分取出数据，加入到有序的部分，直到整个排序完成

例如：序列[5, 7, 2, 3, 6]

1. 分为有序的序列和无序的序列 (5) (7 2 3 6)
2. 不断的扩充有序序列 (5 7) (2 3 6)
3. 不断的扩充有序序列 (2 5 7) (3 6)
4. 不断的扩充有序序列 (2 3 5 7) (6)
5. 不断的扩充有序序列 (2 3 5 6 7)
6. 排序完成

代码

/**
 * 通常人们整理桥牌的方法是一张一张的来，将每一张牌插入到其它已经有序的牌中的适当位置。
 * 在计算机的实现中，为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。
 * 这种算法叫做插入算法
 */
function insertSort(arr) {
  let len = arr.length;
  for (let i = 1; i < len; i++) {
    for (let j = i; j > 0; j--) {
      if (arr[j] < arr[j - 1]) {
        // 当前元素比前一个元素小，则交换
        swap(arr, j, j - 1);
      }else{
        // 当前元素比前一个元素大，说明当前位置即为适当的位置，直接退出此次循环
        break; 
      }
    }
  }
  console.log(arr)
}
// 交换数组指定位置的值
function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}