插入排序（Insertion Sort）是一种简单的排序算法，它的工作原理是通过逐一将未排序的元素插入到已排序的序列中，直到整个序列都有序。

插入排序的步骤如下：

  1. 从第二个元素开始（索引为 1），将当前元素作为 key
  2. 与 key 之前的元素进行比较，如果之前的元素大于 key，则将其向后移动一位。
  3. 重复步骤 2，直到找到一个小于或等于 key 的元素。
  4. 将 key 插入到该位置。
  5. 重复步骤 1-4，直到整个序列都有序。

demo

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
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)）
  • 不适合大型数据集的排序
  • 不适合需要高效率的场景

插入排序可以用于以下场景：

  • 小规模数据集的排序
  • 需要稳定排序的场景
  • 需要简单易懂的排序算法