直接插入排序：
什么是直接插入排序？
每一趟將一個(gè)待排序的記錄，按照其關(guān)鍵字的大小插入到有序隊(duì)列的合適位置里，直到全部插入完成。
通俗解釋一波：
打牌為例：
先拿一張5在手里，
再摸到一張4，比5小，插到5前面，
摸到一張6，嗯，比5大，插到5后面，
摸到一張8，比6大，插到6后面，
。。。
嗯，等你最后一張牌插完，你發(fā)現(xiàn)所有牌都有順序了（這個(gè)只對(duì)按順序插牌的同學(xué)有效~~~~）
圖片解釋一波：
代碼基本思路：
待排序記錄 R1，R2，… ，Rn–1, Rn
第一步:R1
第二步:(R1 ), R2
第三步:(R1 , R2), R3
……
第 j 步:(R1，R2，… ，Rj–1), Rj
……
第 n 步: (R1，R2，… ，Rn–1), Rn.
例:j=5
原有序表中關(guān)鍵詞比Rj大的記錄數(shù):dj
比較次數(shù):dj+1 移動(dòng)次數(shù): dj+2
Java代碼實(shí)現(xiàn)：
public class SortTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] sort = { 4, 5, 6, 7, 9 };
insertSort(sort);
}
public static void insertSort(int[] list) {
// 第1個(gè)數(shù)肯定是有序的，從第2個(gè)數(shù)開始遍歷，依次插入有序序列
for (int i = 1; i < list.length; i++) {
int j = 0;
int temp = list[i]; // 取出第i個(gè)數(shù)，和前i-1個(gè)數(shù)比較后，插入合適位置
// 因?yàn)榍癷-1個(gè)數(shù)都是從小到大的有序序列，所以只要當(dāng)前比較的數(shù)(list[j])比temp大，就把這個(gè)數(shù)后移一位
for (j = i - 1; j >= 0 && temp < list[j]; j--) {
list[j + 1] = list[j];
}
list[j + 1] = temp;
}
//處處排序后的結(jié)果
for (int i : list) {
System.out.println(i);
}
}
}
輸入序列：
sort = { 4, 3, 6, 1, 9 };
輸出結(jié)果：
1
3
4
6
9
算法性能分析：
時(shí)間復(fù)雜度：
當(dāng)數(shù)據(jù)正序時(shí)，執(zhí)行效率最好，每次插入都不用移動(dòng)前面的元素，時(shí)間復(fù)雜度為O(N)。
當(dāng)數(shù)據(jù)反序時(shí)，執(zhí)行效率最差，每次插入都要前面的元素后移，時(shí)間復(fù)雜度為O(N2)。
所以，數(shù)據(jù)越接近正序，直接插入排序的算法性能越好。
空間復(fù)雜度：
由直接插入排序算法可知，我們在排序過程中，需要一個(gè)臨時(shí)變量存儲(chǔ)要插入的值，所以空間復(fù)雜度為1。
算法穩(wěn)定性：
直接插入排序的過程中，不需要改變相等數(shù)值元素的位置，所以它是穩(wěn)定的算法。
