1、算法思想
將一個記錄插入到已排序好的有序表中，從而得到一個新的記錄數增1的有序表。
即：先將序列的第1個記錄看成是一個有序的子序列，然后從第2個記錄逐個進行插入，直至整個序列有序為止。
要點：設立哨兵，作為臨時存儲和判斷數組邊界之用。
2、代碼實現
~~~
package sort;
public class StraightInsertSort {
public static void main(String[] args) {
int[] source = {99, 53, 27, 36, 15, 69, 42, 66};
printArr(source);
StraightInsertSort(source);
printArr(source);
}
/**
* 將一個記錄插入到已排序好的有序表中，從而得到一個新的記錄數增1的有序表。 即：先將序列的第1個記錄看成是一個有序的子序列，然后從第2個記錄逐個進行插入，直至整個序列有序為止。 要點：設立哨兵，作為臨時存儲和判斷數組邊界之用。
*/
private static void StraightInsertSort(int[] source) {
if (source.length <= 1 || source == null) {
return;
}
int j;
for (int i = 1; i < source.length; i++) { // 從第二個數開始，依次直接插入
j = i;// 亦可只用一個變量i，但會增加比較次數
while (j > 0 && source[j] < source[j - 1]) {// 位置不合適則交換
source[j] = source[j - 1] + (source[j - 1] = source[j]) * 0;
j--;
}
printArr(source);
}
}
private static void printArr(int[] source) {
for (int i : source) {
System.out.print(i + " ");
}
System.out.println();
}
}
~~~
3、算法分析
### 算法穩定性
如果碰見一個和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩定的。
如果目標是把n個元素的序列升序排列，那么采用插入排序存在最好情況和最壞情況如下。
**最好情況**：序列已經是升序排列了，在這種情況下，需要進行的比較操作需(n-1)次即可。
**最壞情況**：序列是降序排列，那么此時需要進行的比較共有n(n-1)/2次（計算式為1+2+……+ n-1）。
直接插入排序屬于穩定的排序，**最壞時間復雜度**為**O(n^2)**，**最好時間復雜度**為**O(n)**，**空間復雜度**為**O(1)**。
插入排序的賦值操作是比較操作的次數加上(n-1)次。
因此，插入排序**不適合對于數據量比較大**的排序應用。
源碼地址：[https://github.com/zxiaofan/Algorithm/blob/master/src/sort/StraightInsertSort.java](https://github.com/zxiaofan/Algorithm/blob/master/src/sort/StraightInsertSort.java)
