插入排序（Insertion Sort）是一種簡(jiǎn)單直觀的排序算法莱睁。它的工作原理是通過(guò)構(gòu)建有序序列惨好，對(duì)于未排序的數(shù)據(jù)疚膊，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上衣撬，通常采用 in-place 排序（原地排序乖订，即只需用到 的額外空間的排序），因而在從后向前掃描過(guò)程中具练，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間甜无。
執(zhí)行過(guò)程
- 從第一個(gè)元素開(kāi)始扛点，將該元素放入子數(shù)組，此時(shí)子數(shù)組可以認(rèn)為已經(jīng)被排序岂丘；
- 取出下一個(gè)元素陵究，在已經(jīng)排序的元素序列中從后向前掃描；
- 如果該元素（已排序）大于新元素奥帘，將該元素移到下一位置铜邮；
- 重復(fù)步驟 3，直到找到已排序的元素小于或者等于新元素的位置寨蹋；
- 將新元素插入到該位置之后松蒜；
- 重復(fù)步驟 2~5，直至子數(shù)組的元素個(gè)數(shù)和原數(shù)組相同已旧。
插入排序的偽代碼實(shí)現(xiàn)如下：
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
使用循環(huán)不變式來(lái)理解算法的正確性
- 初始化：首先秸苗，可以看出，在第一次循環(huán)迭代之前（當(dāng) j=2 時(shí)）运褪，子數(shù)組 A[1..j-1] 只有一個(gè)元素 A[1]惊楼，因此，循環(huán)不變式成立秸讹。
- 保持：接著檀咙，處理第二條性質(zhì)：證明每次迭代保持循環(huán)不變式。在 for 循環(huán)體的第 4～7 行將 A[j-1]璃诀、A[j-2]弧可、A[j-3] 等向右移動(dòng)一個(gè)位置，直到找到 A[j] 的適當(dāng)位置文虏，第 8 行將 A[j] 的值插入該位置侣诺。此時(shí)，子數(shù)組 A[1..j] 由原來(lái)在 A[1..j] 中的元素組成氧秘，但已按序排列年鸳。那么對(duì) for 循環(huán)的下一次迭代增加 j 將保持循環(huán)不變式。
- 終止：最后丸相，研究在循環(huán)終止時(shí)發(fā)生了什么搔确。導(dǎo)致 for 循環(huán)終止的條件是 j>A.length=n。因?yàn)槊看窝h(huán)迭代 j 增加 1，那么必有 j=n+1膳算。在循環(huán)不變式的表述中將 j 用 n+1 代替座硕，最終：子數(shù)組 A[1..n] 由原來(lái)在 A[1..n]中的元素組成，但已按序排列涕蜂，即子數(shù)組 A[1..n] 就是整個(gè)數(shù)組已排序的結(jié)果华匾，因此算法正確。
算法分析
我們首先給出 INSERTION-SORT 中机隙，每條語(yǔ)句的執(zhí)行時(shí)間和執(zhí)行次數(shù)蜘拉。
該算法的運(yùn)行時(shí)間是執(zhí)行每條語(yǔ)句的運(yùn)行時(shí)間之和。即有鹿，在具有 n 個(gè)值的輸入時(shí)旭旭，INSERTION-SORT 的運(yùn)行時(shí)間
當(dāng)出現(xiàn)最佳情況時(shí)（輸入數(shù)組已排好序），算法的運(yùn)行時(shí)間
此時(shí)葱跋，我們可以把運(yùn)行時(shí)間表示為 持寄，其中常量 a 和 b 依賴(lài)于語(yǔ)句代價(jià)
。因此娱俺，它是 n 的線性函數(shù)稍味。
當(dāng)出現(xiàn)最壞情況時(shí)（輸入數(shù)組已反向排序），每個(gè)元素 A[j] 都會(huì)與整個(gè)已排序的子數(shù)組 A[1..j-1] 中的每個(gè)元素進(jìn)行比較矢否，此時(shí)仲闽，
算法的運(yùn)行時(shí)間
此時(shí)，我們可以把運(yùn)行時(shí)間表示為 僵朗，其中常量 a赖欣、b 和 c 依賴(lài)于語(yǔ)句代價(jià)
。因此验庙，它是 n 的二次函數(shù)顶吮。
算法復(fù)雜度
上面，我們已經(jīng)分析了插入排序的最好情況和最壞情況粪薛。最好情況就是悴了，序列已經(jīng)是升序排列了，在這種情況下违寿，需要進(jìn)行的比較操作需進(jìn)行 次湃交；最壞情況就是，序列是降序排列藤巢，那么此時(shí)需要進(jìn)行的比較共有
次搞莺。插入排序的賦值操作是比較操作的次數(shù)減去
次，（因?yàn)?
次循環(huán)中掂咒，每一次循環(huán)的比較都比賦值多一個(gè)才沧，多在最后那一次比較并不帶來(lái)賦值）迈喉。平均來(lái)說(shuō)插入排序算法復(fù)雜度為
。因而温圆，插入排序不適合對(duì)于數(shù)據(jù)量比較大的排序應(yīng)用挨摸。但是，如果需要排序的數(shù)據(jù)量很小岁歉，例如得运，量級(jí)小于千；或者若已知輸入元素大致上按照順序排列刨裆，那么插入排序還是一個(gè)不錯(cuò)的選擇澈圈。 插入排序在工業(yè)級(jí)庫(kù)中也有著廣泛的應(yīng)用，在 STL 的 sort 算法和stdlib 的 qsort 算法中帆啃，都將插入排序作為快速排序的補(bǔ)充，用于少量元素的排序（通常為8個(gè)或以下）窍帝。
代碼實(shí)現(xiàn)
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 {
// 對(duì) arr 進(jìn)行拷貝努潘，不改變參數(shù)內(nèi)容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
// 從下標(biāo)為1的元素開(kāi)始選擇合適的位置插入，因?yàn)橄聵?biāo)為0的只有一個(gè)元素坤学，默認(rèn)是有序的
for (int i = 1; i < arr.length; i++) {
// 記錄要插入的數(shù)據(jù)
int tmp = arr[i];
// 從已經(jīng)排序的序列最右邊的開(kāi)始比較疯坤，找到比其小的數(shù)
int j = i;
while (j > 0 && tmp < arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}
// 存在比其小的數(shù)，插入
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;
}
}
參考文獻(xiàn)
- 《算法導(dǎo)論 第三版》
- 維基百科
- 菜鳥(niǎo)教程
