插入排序

局部有序

补充

补充：插入排序（Insertion Sort）将数组分为"已排序区"与"未排序区"，每次从未排序区取一个元素，向左扫描找到它在已排序区中的插入位置。已排序区始终保持局部有序，n-1 轮后整体有序。最佳情况（已排序）时间 O(n)，最差 O(n²)，是稳定排序、原地操作。实际工程中常用作小区间排序（V8 sort 在小数组上使用插入排序）。

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

来源整理自：我的有道云笔记