5
20
50
慢
中等
快
排序可视化
排序过程
算法详情
直接插入排序 (Insertion Sort)
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
时间复杂度
O(n²)
空间复杂度
O(1)
稳定性
稳定
适用于小规模数据或基本有序的数据。
算法代码
// 直接插入排序代码
function insertionSort(arr) {
const n = arr.length;
for (let i = 1; i < n; i++) {
let key = arr[i];
let j = i - 1;
// 将大于key的元素向后移动
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// 插入key
arr[j + 1] = key;
}
return arr;
}
算法比较
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
|
直接插入排序
|
O(n²) | O(n²) | O(1) | 稳定 | 小规模数据或基本有序数据 |
|
折半插入排序
|
O(n²) | O(n²) | O(1) | 稳定 | 小规模数据，减少比较次数 |
|
希尔排序
|
O(n log n) 到 O(n²) | O(n²) | O(1) | 不稳定 | 中等规模数据 |
|
冒泡排序
|
O(n²) | O(n²) | O(1) | 稳定 | 教学演示 |
|
快速排序
|
O(n log n) | O(n²) | O(log n) | 不稳定 | 大规模数据 |
|
简单选择排序
|
O(n²) | O(n²) | O(1) | 不稳定 | 小规模数据 |
|
堆排序
|
O(n log n) | O(n log n) | O(1) | 不稳定 | 大规模数据，需要稳定性能 |
|
归并排序
|
O(n log n) | O(n log n) | O(n) | 稳定 | 大规模数据，需要稳定性 |
|
基数排序
|
O(k·n) | O(k·n) | O(n+k) | 稳定 | 整数排序 |