x-note
Search…
插入排序
插入排序(Insertion Sort)的工作原理是通过构建有序序列,对于未排序数据,在一排序序列中扫描,找到相应位置并插入。
  • 平均时间复杂度:
    O(n2)O(n^2)
  • 最好时间复杂度:
    O(n)O(n)
  • 最坏时间复杂度:
    O(n2)O(n^2)
  • 空间复杂度:
    O(1)O(1)
  • 稳定性:稳定
  • 排序方式:原地(In-place)
运作方式:
  1. 1.
    将第一个元素放入有序序列中
  2. 2.
    取出下一个元素,(从后向前)扫描已排序的元素序列
  3. 3.
    如果该元素大于新元素,将该元素移到下一个位置
  4. 4.
    重复步骤 3,直到找到该元素在已排序数组中的位置
  5. 5.
    将新元素插入到该位置
  6. 6.
    重复步骤 2~5
Could not load image
具体实现:
function insertSort(arr) {
for (let i = 1; i < arr.length; ++i) {
let tmp = arr[i]; // 减少索引访问
// 数组的 0~i-1 部分,即已排序序列
for (let j = i - 1; j >= 0; --j) {
if (tmp < arr[j]) {
arr[j + 1] = arr[j];
arr[j] = tmp;
}
}
}
return arr;
}
Copy link