插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法厕怜。它的工作原理是通過構建有序序列，對于未排序數(shù)據(jù)蕾总，在已排序序列中從后向前掃描粥航，找到相應位置并插入。插入排序在實現(xiàn)上生百，通常采用in-place排序（即只需用到O(1)的額外空間的排序）递雀，因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位蚀浆，為最新元素提供插入空間缀程。
算法描述
具體算法描述如下：
從第一個元素開始，該元素可以認為已經(jīng)被排序市俊；
取出下一個元素杨凑，在已經(jīng)排序的元素序列中從后向前掃描；
如果該元素（已排序）大于新元素摆昧，將該元素移到下一位置撩满；
重復步驟3，直到找到已排序的元素小于或者等于新元素的位置；
將新元素插入到該位置后伺帘；
重復步驟2~5昭躺。
動圖展示：
動圖展示
public static int[] insertionSort(int[] array) {
if (array.length == 0)
return array;
int current;
for (int i = 0; i < array.length - 1; i++) {
current = array[i + 1];
int preIndex = i;
while (preIndex >= 0 && current < array[preIndex]) {
array[preIndex + 1] = array[preIndex];
preIndex--;
}
array[preIndex + 1] = current;
}
return array;
}
