插入排序(Insertion Sort)是一种简单直观的排序算法,它的工作原理类似于整理扑克牌。
插入排序通过构建有序序列,对于未排序的数据,在已排序序列中从后向前扫描,找到相应位置并插入。
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂。
插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。
1. 算法步骤
初始化:将列表分为已排序部分和未排序部分。初始时,已排序部分只包含第一个元素,未排序部分包含剩余元素。
选择元素:从未排序部分中取出第一个元素。
插入到已排序部分:将该元素与已排序部分的元素从后向前依次比较,找到合适的位置插入。
重复步骤:重复上述步骤,直到未排序部分为空,列表完全有序。
2. 动图演示
假设有一个待排序的列表 [5, 2, 4, 6, 1, 3],插入排序的过程如下:
初始状态:
已排序部分:
[5]
。未排序部分:
[2, 4, 6, 1, 3]
。
第一轮:
取出未排序部分的第一个元素
2
。将
2
与已排序部分的5
比较,2 < 5
,插入到5
前面。列表变为
[2, 5, 4, 6, 1, 3]
。已排序部分:
[2, 5]
,未排序部分:[4, 6, 1, 3]
。
第二轮:
取出未排序部分的第一个元素
4
。将
4
与已排序部分的5
比较,4 < 5
,继续与2
比较,4 > 2
,插入到2
和5
之间。列表变为
[2, 4, 5, 6, 1, 3]
。已排序部分:
[2, 4, 5]
,未排序部分:[6, 1, 3]
。
第三轮:
取出未排序部分的第一个元素
6
。将
6
与已排序部分的5
比较,6 > 5
,直接插入到末尾。列表变为
[2, 4, 5, 6, 1, 3]
。已排序部分:
[2, 4, 5, 6]
,未排序部分:[1, 3]
。
第四轮:
取出未排序部分的第一个元素
1
。将
1
与已排序部分的6
比较,1 < 6
,继续与5
、4
、2
比较,1
是最小的,插入到最前面。列表变为
[1, 2, 4, 5, 6, 3]
。已排序部分:
[1, 2, 4, 5, 6]
,未排序部分:[3]
。
第五轮:
取出未排序部分的第一个元素
3
。将
3
与已排序部分的6
比较,3 < 6
,继续与5
、4
、2
比较,3 > 2
,插入到2
和4
之间。列表变为
[1, 2, 3, 4, 5, 6]
。已排序部分:
[1, 2, 3, 4, 5, 6]
,未排序部分为空。
实例
n = len(arr)
for i in range(1, n):
key = arr[i] # 取出未排序部分的第一个元素
j = i - 1
# 将 key 插入到已排序部分的正确位置
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j] # 向后移动元素
j -= 1
arr[j + 1] = key # 插入 key
return arr
# 示例
arr = [5, 2, 4, 6, 1, 3]
sorted_arr = insertion_sort(arr)
print(sorted_arr) # 输出: [1, 2, 3, 4, 5, 6]
时间复杂度
-
最坏情况:O(n²),当列表是逆序时,每次插入都需要移动所有已排序元素。
-
最好情况:O(n),当列表已经有序时,只需遍历一次列表。
-
平均情况:O(n²)。
空间复杂度
-
O(1),插入排序是原地排序算法,不需要额外的存储空间。
优缺点
-
优点:
-
实现简单,代码易于理解。
-
对小规模数据或基本有序的数据效率较高。
-
原地排序,不需要额外的存储空间。
-
稳定排序算法(相同元素的相对顺序不会改变)。
-
-
缺点:
-
时间复杂度较高,不适合大规模数据集。
-
适用场景
-
数据量较小或基本有序的场景。
-
需要稳定排序算法的场景。
-
作为更复杂排序算法(如快速排序、归并排序)的辅助算法。
代码实现
JavaScript
实例
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
return arr;
}
Python
实例
for i in range(len(arr)):
preIndex = i-1
current = arr[i]
while preIndex >= 0 and arr[preIndex] > current:
arr[preIndex+1] = arr[preIndex]
preIndex-=1
arr[preIndex+1] = current
return arr
Go
实例
for i := range arr {
preIndex := i - 1
current := arr[i]
for preIndex >= 0 && arr[preIndex] > current {
arr[preIndex+1] = arr[preIndex]
preIndex -= 1
}
arr[preIndex+1] = current
}
return arr
}
Java
实例
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝,不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
// 从下标为1的元素开始选择合适的位置插入,因为下标为0的只有一个元素,默认是有序的
for (int i = 1; i < arr.length; i++) {
// 记录要插入的数据
int tmp = arr[i];
// 从已经排序的序列最右边的开始比较,找到比其小的数
int j = i;
while (j > 0 && tmp < arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}
// 存在比其小的数,插入
if (j != i) {
arr[j] = tmp;
}
}
return arr;
}
}
PHP
实例
{
$len = count($arr);
for ($i = 1; $i < $len; $i++) {
$preIndex = $i - 1;
$current = $arr[$i];
while($preIndex >= 0 && $arr[$preIndex] > $current) {
$arr[$preIndex+1] = $arr[$preIndex];
$preIndex--;
}
$arr[$preIndex+1] = $current;
}
return $arr;
}
C
实例
int i,j,key;
for (i=1;i<len;i++){
key = arr[i];
j=i-1;
while((j>=0) && (arr[j]>key)) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
C++
实例
for(int i=1;i<len;i++){
int key=arr[i];
int j=i-1;
while((j>=0) && (key<arr[j])){
arr[j+1]=arr[j];
j--;
}
arr[j+1]=key;
}
}
C#
实例
{
for(int i = 1;i < array.length;i++)
{
int temp = array[i];
for(int j = i - 1;j >= 0;j--)
{
if(array[j] > temp)
{
array[j + 1] = array[j];
array[j] = temp;
}
else
break;
}
}
}
Swift
实例
let temp = arr[i]
for j in (0..<i).reversed() {
if arr[j] > temp {
arr.swapAt(j, j+1)
}
}
}
原文地址:https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/3.insertionSort.md
参考地址:https://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F
Mr.Sugarcane
843***601@qq.com
我编写了Lua的版本:
Mr.Sugarcane
843***601@qq.com
kezhuoquan
kez***quan@163.com
rust 版本:
kezhuoquan
kez***quan@163.com
sujiujiu
suj***iu123@gmail.com
Python 的用 while 这样会更好一些:
或者用 for,就是 preIndex:
sujiujiu
suj***iu123@gmail.com