基本思想
將一個記錄插入到已排序好的有序表中典格，從而得到一個新記錄數(shù)增1的有序表。即：先將序列的第1個記錄看成是一個有序的子序列，然后從第2個記錄逐個進行插入丰刊，直至整個序列有序為止泽裳。
要點：設(shè)置哨兵瞒斩，作為臨時存儲和判斷數(shù)組邊界之用。
直接插入排序示例：
1EB9AC87-DB31-4A40-AA75-D5D4A01FCF4D.png
如果碰到一個和插入元素相等的涮总，那么插入元素把想插入的元素放在相等元素的后面胸囱。所以，相等元素的前后順序沒有改變瀑梗，從原無序序列出去的順序就是排好序后的順序烹笔，所以插入順序是穩(wěn)定的裳扯。
Java 代碼
public static void insertSort(int[] arr) {
if (null == arr || arr.length <= 1) {
return;
}
int i, j;
int n = arr.length;
int target;
for (i = 1; i < n; i++) {
j = i-1;
target = arr[i];
while (j >= 0 && target < arr[j]) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = target;
}
}
效率分析
穩(wěn)定
空間復(fù)雜度O(1)
時間復(fù)雜度O(nn)
最差情況下：反序，需要移動n(n-1)/2個元素
最好情況：正序谤职，不需要移動元素
