插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序（原地排序，即只需用到 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
执行过程
- 从第一个元素开始，将该元素放入子数组，此时子数组可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置之后；
- 重复步骤 2~5，直至子数组的元素个数和原数组相同。
插入排序的伪代码实现如下：
INSERTION-SORT(A)
1 for j = 2 to A.length
2 key = A[j]
3 // Insert A[j] into the sorted sequence A[1..j-1].
4 i = j - 1
5 while i > 0 and A[i] > key
6 A[i+1] = A[i]
7 i = i - 1
8 A[i + 1] = key
使用循环不变式来理解算法的正确性
- 初始化：首先，可以看出，在第一次循环迭代之前（当 j=2 时），子数组 A[1..j-1] 只有一个元素 A[1]，因此，循环不变式成立。
- 保持：接着，处理第二条性质：证明每次迭代保持循环不变式。在 for 循环体的第 4～7 行将 A[j-1]、A[j-2]、A[j-3] 等向右移动一个位置，直到找到 A[j] 的适当位置，第 8 行将 A[j] 的值插入该位置。此时，子数组 A[1..j] 由原来在 A[1..j] 中的元素组成，但已按序排列。那么对 for 循环的下一次迭代增加 j 将保持循环不变式。
- 终止：最后，研究在循环终止时发生了什么。导致 for 循环终止的条件是 j>A.length=n。因为每次循环迭代 j 增加 1，那么必有 j=n+1。在循环不变式的表述中将 j 用 n+1 代替，最终：子数组 A[1..n] 由原来在 A[1..n]中的元素组成，但已按序排列，即子数组 A[1..n] 就是整个数组已排序的结果，因此算法正确。
算法分析
我们首先给出 INSERTION-SORT 中，每条语句的执行时间和执行次数。
该算法的运行时间是执行每条语句的运行时间之和。即，在具有 n 个值的输入时，INSERTION-SORT 的运行时间
当出现最佳情况时（输入数组已排好序），算法的运行时间
此时，我们可以把运行时间表示为 ，其中常量 a 和 b 依赖于语句代价
。因此，它是 n 的线性函数。
当出现最坏情况时（输入数组已反向排序），每个元素 A[j] 都会与整个已排序的子数组 A[1..j-1] 中的每个元素进行比较，此时，
算法的运行时间
此时，我们可以把运行时间表示为 ，其中常量 a、b 和 c 依赖于语句代价
。因此，它是 n 的二次函数。
算法复杂度
上面，我们已经分析了插入排序的最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需进行 次；最坏情况就是，序列是降序排列，那么此时需要进行的比较共有
次。插入排序的赋值操作是比较操作的次数减去
次，（因为
次循环中，每一次循环的比较都比赋值多一个，多在最后那一次比较并不带来赋值）。平均来说插入排序算法复杂度为
。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千；或者若已知输入元素大致上按照顺序排列，那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用，在 STL 的 sort 算法和stdlib 的 qsort 算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。
代码实现
JavaScript
function insertionSort(arr) {
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
def insertionSort(arr):
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
func insertionSort(arr []int) []int {
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
public class InsertSort implements IArraySort {
@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;
}
}
C
void insertion_sort(int arr[], int len){
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++
void insertion_sort(int arr[],int len){
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;
}
}
网友评论