# 0. 前言
插入排序基本假設為當前位置的前面的元素的序列是基本有序的。然后再查找其再前面序列中的邏輯有序位置，最終放置元素到目標位置即可。
# 1. 簡單插入排序
~~~
public void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int index = i - 1;
int value = arr[i];
while (index >= 0 && value < arr[index]) {
arr[index + 1] = arr[index];
index--;
}
arr[index + 1] = value;
}
}
~~~
# 2. 希爾排序
值得注意的是，上面的簡單插入排序中的步長為`1`，這里的步長每次都在減半，直到步長為`0`。
~~~
public void shellSort(int[] arr) {
for (int d = arr.length / 2; d > 0; d = d / 2) {
for (int j = d; j < arr.length; j++) {
int index = j - d;
int value = arr[j];
while (index >=0 && arr[index] > value) {
arr[index + d] = arr[index];
index -= d;
}
arr[index + d] = value;
}
}
}
~~~
# 3. 折半插入排序
采用二分查找的方式來找目標位置，對于帶排序數據量比較多的時候，效率還是比較高的。
~~~
public void binaryInsertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int value = arr[i];
int left = 0;
int right = i - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] > value) {
right = mid - 1;
}
if (arr[mid] < value) {
left = mid + 1;
}
}
for (int j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = value;
}
}
~~~
