第 88 期(算法-排序)：经典排序算法之插入排序 #91
Description
插入排序
插入排序（Insertion sort）是一种简单直观且稳定的排序算法。
- 原理： 将每次插入的数和之前已经完成排序的序列进行重新排序。
- 复杂度： 时间复杂度：O(n²)，空间复杂度：O(1)
- 稳定性： 选插入排序是稳定的排序算法。
function insertionSort(arr) {
// 注意这里是从 arr[1] 开始的
for (var i = 1; i < arr.length; i++) {
var preIndex = i - 1;
var current = arr[i];
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}