插入排序 - 算法演示

算法原理

插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

核心思想：

从第一个元素开始，该元素可以认为已经被排序。
取出下一个元素，在已经排序的元素序列中从后向前扫描。
如果该元素（已排序）大于新元素，将该元素移到下一位置。
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
将新元素插入到该位置后。

演示

速度:

点击"开始排序"以观察算法执行过程

for (int i = 1; i < n; i++) {
 int key = arr[i]; // 当前待插入元素
 int j = i - 1;
 while (j >= 0 && arr[j] > key) {
 arr[j + 1] = arr[j]; // 元素后移
 j--;
 }
 arr[j + 1] = key; // 插入到正确位置
}

算法分析

特性	描述
时间复杂度	O(n²) - 平均和最坏情况；但如果数组基本有序，接近 O(n)
空间复杂度	O(1) - 只需要常数级的额外空间
稳定性	稳定 - 相等元素不会交换相对位置