插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中,從而得到一個新的、個數加一的有序數據。比較和交換的時間復雜度為O(n^2)，算法自適應，對于數據已基本有序的情況，時間復雜度為O(n)，算法穩定，開銷很低。算法適合于數據已基本有序或者數據量小的情況。

插入算法把要排序的數組分成兩部分：***部分包含了這個數組的所有元素，但將***一個元素除外，而第二部分就只包含這一個元素。在***部分排序后，再把這個***元素插入到此刻已是有序的***部分里的位置。

算法描述

一般來說，插入排序都采用in-place在數組上實現。具體算法描述如下： 　　

1. 從***個元素開始，該元素可以認為已經被排序 　　

2. 取出下一個元素，在已經排序的元素序列中從后向前掃描 　　

3. 如果該元素（已排序）大于新元素，將該元素移到下一位置 　　

4. 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置 　　

5. 將新元素插入到下一位置中 　　

6. 重復步驟2 　　

如果比較操作的代價比交換操作大的話，可以采用二分查找法來減少比較操作的數目。該算法可以認為是插入排序的一個變種，稱為二分查找排序。

代碼實現

public void insertionSort() {// 插入排序  
int out, in;  
int count1 = 0, count2 = 0;// 復制次數，比較次數  
for (out = 1; out < nElems; out++) {  
long temp = a[out];  
in = out;  
boolean flag=in>0&&a[in-1]>=temp;  
while(flag){  
if(a[in-1]>=temp){  
if(in>0){  
a[in]=a[in-1];  
count1++;  
--in;   
}  
}  
count2++;  
flag=in>0&&a[in-1]>=temp;  
}   
a[in] = temp;  
}  
System.out.println("復制次數為：" + count1 + " 比較次數為：" + count2);  
} 

插入排序法在數據已有一定順序的情況下，效率較好。但如果數據無規則，則需要移動大量的數據，其效率就與冒泡排序法和選擇排序法一樣差了。

【編輯推薦】

1. 18.1.4 插入排序法
2. 介紹C#直接插入排序
3. 經典四講貫通C++排序之一 插入排序