核心思想:对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入
步骤:
- 从第二个元素开始,认为第一个元素是已排序部分
- 取出下一个元素,在已排序部分从后向前扫描
- 如果已排序部分的元素大于新元素,将已排序部分的元素向右移动一位
- 重复步骤3,直到找到已排序部分中小于或等于新元素的位置
- 将新元素插入到该位置
- 重复以上步骤,直到所有元素排序完成
分析:
- 时间复杂度: 最坏时间复杂度是 O(n^2),因为最坏情况下需要进行 n(n−1)/2 次比较和移动
- 空间复杂度: 原地排序算法,空间复杂度是 O(1)
实现代码
function insertionSort(arr) {
let n = arr.length;
for (let i = 1; i < n; i++) {
let key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
return arr;
}
let array = [5, 3, 8, 4, 2];
console.log(insertionSort(array)); // 输出: [2, 3, 4, 5, 8]