插入排序（復(fù)雜度為O(n2) ）
插入排序是一種最簡(jiǎn)單的排序方法怔软，它的基本思想是將一個(gè)記錄插入到已經(jīng)排好序的有序表中姜性，
從而一個(gè)新的猪叙、記錄數(shù)增1的有序表。在其實(shí)現(xiàn)過程使用雙層循環(huán)夹囚，
外層循環(huán)對(duì)除了第一個(gè)元素之外的所有元素纵刘，
內(nèi)層循環(huán)對(duì)當(dāng)前元素前面有序表進(jìn)行待插入位置查找，并進(jìn)行移動(dòng)荸哟；
動(dòng)圖演示
insertionSort.gif
總結(jié)：
缺點(diǎn)假哎；當(dāng)需要插入的數(shù)據(jù)較小時(shí)，后移的次數(shù)明顯增多鞍历，影響性能舵抹。
因此產(chǎn)生了希爾排序。
代碼實(shí)現(xiàn)（java）
/**
* 插入排序：從數(shù)組中逐個(gè)元素作為插入元素劣砍，和前面的進(jìn)行比較惧蛹，小的即插入前面。
* 前面的已經(jīng)是排序了刑枝。
*
* @param arr 需要排序的數(shù)組(從小到大排序）
*/
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
// 插入的下標(biāo)香嗓，默認(rèn)是前一位
int insertIndex = i - 1;
// 插入的值
int insertValue = arr[i];
// 插入的值和前面的進(jìn)行比較，小則插入装畅。排序：從小到大靠娱，改大于號(hào)則排序?yàn)閺拇蟮叫? while (insertIndex >= 0 && insertValue < arr[insertIndex]){
// 交換，將小的放前面掠兄，保證前面是已經(jīng)排序后的
arr[insertIndex + 1] = arr[insertIndex];
insertIndex --;
}
if(insertIndex != i - 1) {
arr[insertIndex + 1] = insertValue;
}
// System.out.println("第" + i + "輪：" + Arrays.toString(arr));
}
}
