一.直接插入排序原理
1.插入排序算法首先要把排序的數組分成兩部分：第一部分是這個數組中所有已排序元素，而第二部分就是未排序的元素（即待插入元素）。
2.将待插入元素和已排序的元素逐一比較，若待插入的元素大，則直接将該元素算入已排序的元素中，否則交換兩元素的位置，并且待插入元素繼續和前一個元素進行比較，直到不需要交換元素位置後，将該元素算入已排序的元素中。
3.重複執行步驟2，直到未排序的元素個數為0。
插入排序的基本思想是：每步将一個待排序的記錄，按其關鍵碼值的大小插入前面已經排序的檔案中适當位置上，直到全部插入完為止。
插入排序是一個穩定的排序算法。
二.直接插入排序時間複雜度
最壞情況下，數組完全逆序，插入第2個元素時要考察前1個元素，插入第3個元素時，要考慮前2個元素，……，插入第N個元素，要考慮前 N - 1個元素。是以，最壞情況下的比較次數是1 + 2 + 3 + ... + (N-1)，求和為 n2/2 - n / 2，忽略系數，取最高指數項，是以最壞情況下的複雜度為O(n2)。
最好情況下，數組已經是有序的，每插入一個元素，隻需要考查前一個元素，是以最好情況下的時間複雜度為O(n)。
三.直接插入排序代碼實作
public static void main(String[] args) {
int[] arr = {1,6,5,2,4,3,7,9,8};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
//插入的元素(從第二個開始，索引為1)
int insert;
//從1開始循環待插入的元素
for(int i = 1; i < arr.length; i++) {
insert = arr[i];
int j;
for(j = i - 1; j >= 0; j--) {
if(arr[j] > insert) {
arr[j+1] = arr[j];
}else{
break;
}
}
arr[j+1] = insert;
}
}
} 測試：運作後輸出結果如下
四.折半插入排序原理
折半插入排序是對直接插入排序的改進。它不去一個個周遊已經排序的元素，而是将插入元素直接和已經排好序的數組的中間元素進行比較，如果插入的元素比較大，那麼插入的元素肯定屬于後半部分，否則屬于前半部分。這樣，不斷周遊縮小範圍，很快就能确定需要插入的位置。
五.折半插入排序時間複雜度
在不是很理想的情況下，折半插入排序算法比直接插入排序算法明顯減少了關鍵字之間比較的次數，是以速度比直接插入排序算法快，但記錄移動的次數沒有變，是以折半插入排序算法的時間複雜度仍然為O(n2)。
折半插入排序算法是一種穩定的排序算法。
六.折半插入排序代碼實作
public static void main(String[] args) {
int[] arr = {5,3,1,7,8,4,2,9,6};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
int size = arr.length;
for (int i = 1; i < size; i++) {
int temp = arr[i];
int begin = 0; // 标記排好序的數組的頭部
int end = i - 1; // 标記排好序數組的尾部
// 隻要頭部一直小于尾部，說明temp還在2個标記範圍内
while (begin <= end) {
// 取2個标記的中間資料的值
int mid = (begin + end) / 2;
// 比較，若比中間值大，則範圍縮小一半
if (temp > arr[mid]) {
begin = mid + 1;
// 否則，範圍也是縮小一半
} else {
end = mid - 1;
}
// 循環結束時，end<begin,即i應該插入到begin所在的索引
}
// 從begin到i，集體後移
for (int j = i; j > begin; j--) {
arr[j] = arr[j - 1];
}
// 插入i
arr[begin] = temp;
}
} 測試：運作後控制台輸出
