插入排序
{% note info simple %} 插入排序（Insertion Sort）是一种简单的排序算法，它的工作原理是通过逐一将未排序的元素插入到已排序的序列中，直到整个序列都有序。 {% endnote %}
插入排序的步骤如下：
- 从第二个元素开始（索引为 1），将当前元素作为
key - 与
key之前的元素进行比较，如果之前的元素大于key，则将其向后移动一位。 - 重复步骤 2，直到找到一个小于或等于
key的元素。 - 将
key插入到该位置。 - 重复步骤 1-4，直到整个序列都有序。
demo
代码
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}
insertionSort([5, 2, 8, 3, 1, 6, 4]);可视化
优缺点
插入排序的特点是：
- 简单易懂
- 稳定排序（不会改变相同元素的相对顺序）
- 对于小规模数据集效率较高
- 时间复杂度为 O(n^2)，因此对于大型数据集效率较低
插入排序的缺点是：
- 时间复杂度较高（O(n^2)）
- 不适合大型数据集的排序
- 不适合需要高效率的场景
插入排序可以用于以下场景：
- 小规模数据集的排序
- 需要稳定排序的场景
- 需要简单易懂的排序算法