03_插入排序

直接插入排序基本思想是每一步将一个待排序的记录,插入到前面已经排好序的有序序列中去,直到插完所有元素为止。

插入排序的平均时间复杂度为 O(n²) ,最坏时间复杂度为 O(n²) ,空间复杂度为 O(1) ,是稳定排序。

点击查看代码
function insertSort(arr) {
  if (!Array.isArray(arr) || arr.length <= 1) return arr;

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

  return arr;
}
Last Updated:
Contributors: hqchqc