97.插入排序
webVueBlog opened this issue · 0 comments
webVueBlog commented
// 原理
// 通过构建有序序列,对于排序的数据,在已知排序序列中从后往前扫描
// 找到相应的位置插入
// 时间复杂度 O(n^2)
function insertSort(arr) {
let n = arr.length;
let preIndex, current;
// 从第一个开始
for (let i = 1; i < n; i++) {
// 前一个元素的位置
preIndex = i - 1;
// 当前元素
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
// 假如 pre cur [1,2]
arr[preIndex + 1] = current;
}
return arr;
}