概述:(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

选择排序

插入排序

分类 数据结构 时间复杂度 最优时间复杂度 平均时间复杂度 空间复杂度
插入排序 数组 О(n²) О(n) О(n²) 总共О(n), 辅助空间 O(1)

使用插入排序为一列数字进行排序的过程
插入排序

代码范例

C语言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void insertion_sort(int arr[], int len) {
int i, j;
int temp;
for (i = 1; i < len; i++) {
temp = arr[i];
//與已排序的數逐一比較,大於temp時,該數向後移
j = i - 1;
// 如果将赋值放到下一行的for循环内, 会导致在第10行出现j未声明的错误
for (; j >= 0 && arr[j] > temp; j--) {
//j循环到-1时,由于[[短路求值]](http://zh.wikipedia.org/wiki/短路求值),不会运算array[-1]
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
//被排序数放到正确的位置
}
}

Python

1
2
3
4
5
6
7
def insert_sort(lst):
n=len(lst)
if n == 1: return lst
for i in range(1, n):
for j in range(i, 0, -1):
if lst[j] < lst[j-1] : lst[j], lst[j-1] = lst[j-1], lst[j]
return lst

Python的另一个版本

1
2
3
4
5
6
7
8
9
10
11
12
def insertion_sort(lst):
if len(lst) == 1:
return lst
for i in range(1, len(lst)):
temp = lst[i]
j = i - 1
while j >= 0 and temp < lst[j]:
lst[j + 1] = lst[j]
j -= 1
lst[j + 1] = temp
return lst

Java

1
2
3
4
5
6
7
8
9
10
11
public static void insertion_sort(int[] arr) {
for(int i = 0; i < arr.length - 1; i++) {
for(int j = i+1; j > 0; j--) {
if(arr[j-1] <= arr[j])
break;
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}

Java的另一个版本

1
2
3
4
5
6
7
8
9
10
11
12
// 将arr[i] 插入到arr[0]...arr[i - 1]中
public static void insertion_sort(int[] arr) {
for (int i = 1; i < arr.length; i++ ) {
int temp = arr[i];
int j = i - 1;
//如果将赋值放到下一行的for循环内, 会导致在第13行出现j未声明的错误
for (; j >= 0 && arr[j] > temp; j-- ) {
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
}

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
Array.prototype.insertion_sort = function() {
var i,j;
for(i = 1;i < this.length; i++) {
for(j = 0; j < i; j++){
if(this[j] > this[i]) {
this.splice(j, 0, this[i]);
this.splice(i+1, 1);
}
}
}
return this;
};

PHP

1
2
3
4
5
6
7
8
9
function insertion_sort(&$arr) {
//php的陣列視為基本型別,所以必須用傳參考才能修改原陣列
for ($i = 1; $i < count($arr); $i++) {
$temp = $arr[$i];
for ($j = $i - 1; $j >= 0 && $arr[$j] > $temp; $j--)
$arr[$j + 1] = $arr[$j];
$arr[$j + 1] = $temp;
}
}

复杂度分析

如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上(n-1)次。平均来说插入排序算法复杂度为О(n²)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用,在STL的sort算法和stdlib的qsort算法中,都将插入排序作为快速排序的补充,用于少量元素的排序(通常为8个或以下)。

参考:https://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F