定義
插入排序（英語：Insertion Sort）是一種簡單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。
插入排序演示動畫1
算法步驟
插入排序算法的運(yùn)作如下：
- 從第一個元素開始，該元素可以認(rèn)為已經(jīng)被排序
- 取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描
- 如果該元素（已排序）大于新元素，將該元素移到下一位置
- 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
- 將新元素插入到該位置后
- 重復(fù)步驟2~5
如果比較操作的代價比交換操作大的話，可以采用二分查找法來減少比較操作的數(shù)目。該算法可以認(rèn)為是插入排序的一個變種，稱為二分查找插入排序。
偽代碼如下：
insertion_sort(array, length)
{
var i, j, temp;
for (i = 1; i < length; i++) {
temp = array[i]; //與已排序的數(shù)逐一比較，大于temp時，該數(shù)向后移
for (j = i - 1; j >= 0 && array[j] > temp; j--)
array[j + 1] = array[j];
array[j+1] = temp; //被排序數(shù)放到正確的位置
}
}
插入排序動畫演示2
代碼實現(xiàn)（java）
/**
*
* @Title: insertSort
* @Description: 插入排序的簡單實現(xiàn)
* @param: @param nums
* @return: void
* @throws
*/
public static void insertSort(int[] nums)
{
for (int i = 1; i < nums.length; i++) {
int value = nums[i];
int j = i - 1;
while (j >= 0 && nums[j] > value) {
nums[j + 1] = nums[j];
j = j - 1;
}
nums[j + 1] = value;
}
}
算法復(fù)雜度分析
如果目標(biāo)是把n個元素的序列升序排列，那么采用插入排序存在最好情況和最壞情況。最好情況就是，序列已經(jīng)是升序排列了，在這種情況下，需要進(jìn)行的比較操作需(n-1)次即可。最壞情況就是，序列是降序排列，那么此時需要進(jìn)行的比較共有n(n-1)/2次。插入排序的賦值操作是比較操作的次數(shù)加上(n-1)次。平均來說插入排序算法復(fù)雜度為O(n2)。因而，插入排序不適合對于數(shù)據(jù)量比較大的排序應(yīng)用。但是，如果需要排序的數(shù)據(jù)量很小，例如，量級小于千，那么插入排序還是一個不錯的選擇。 插入排序在工業(yè)級庫中也有著廣泛的應(yīng)用，在STL的sort算法和stdlib的qsort算法中，都將插入排序作為快速排序的補(bǔ)充，用于少量元素的排序（通常為8個或以下）。
