插入排序的思想是吟逝，先看數(shù)組的第一個(gè)元素帽蝶，把它作為一個(gè)有序序列，再看第二個(gè)元素块攒，與第一個(gè)元素進(jìn)行比較與交換励稳，這樣子前兩個(gè)元素就成為了一個(gè)有序序列。繼續(xù)看第三個(gè)元素局蚀，與第二個(gè)麦锯、第一個(gè)元素進(jìn)行比較、交換琅绅，讓前三個(gè)元素形成一個(gè)有序序列。以此類推...
但是需要注意的是鹅巍，當(dāng)我們要把第n的元素插入時(shí)千扶，需要先與第n-1個(gè)元素比較，如果不小于說(shuō)明第n個(gè)元素的位置已經(jīng)找到了骆捧，為什么呢澎羞，因?yàn)榈趎個(gè)元素前面的元素已經(jīng)是一個(gè)有序序列了，第n個(gè)元素不大于前面的元素敛苇，那么它也不大于其他前面的元素妆绞，所以它所在的位置就是加入它然后成為一個(gè)有序序列的位置顺呕。
// 插入排序
public static void insertionSort(int[] arr) {
// 從1開始循環(huán)，第一個(gè)元素默認(rèn)有序
for (int i = 1; i < arr.length; i++) {
// 為下標(biāo)為i的元素找它的位置
for (int j = i; j > 0; j--) {
// 如果下標(biāo)為i的元素比它前面的元素小
if (arr[j] < arr[j - 1]) {
// 與它前面的元素交換
// 這樣子下標(biāo)為i的元素就到了它的前一個(gè)元素的位置
int swaper = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = swaper;
} else {
// 如果不滿足就說(shuō)明已經(jīng)找到了位置
// 因?yàn)樗懊娴脑亟M成的序列已經(jīng)是有序的了
break;
}
}
}
}
通過(guò)上面的代碼括饶，我們發(fā)現(xiàn)其中有可以優(yōu)化的地方
交換操作要執(zhí)行三個(gè)語(yǔ)句株茶，我們其實(shí)不需要這么多的交換操作，只需要把當(dāng)前要插入的數(shù)字保存起來(lái)图焰，然后看前面的數(shù)字是否大于這個(gè)數(shù)字启盛，如果大于直接覆蓋這個(gè)值就好了，具體看代碼技羔。
// 插入排序的優(yōu)化版本
public static void insertionSort(int[] arr) {
// 從1開始循環(huán)僵闯，第一個(gè)元素默認(rèn)有序
for (int i = 1; i < arr.length; i++) {
// 保存需要插入元素的值
int temp = arr[i];
// j為要插入元素的位置
int j;
for (j = i; j > 0; j--) {
// 如果下標(biāo)為i的元素比它前面的元素小
if (temp < arr[j - 1]) {
arr[j] = arr[j - 1];
} else {
// 如果不滿足就說(shuō)明已經(jīng)找到了位置
// 因?yàn)樗懊娴脑亟M成的序列已經(jīng)是有序的了
break;
}
}
arr[j] = temp;
}
}
這樣子我們循環(huán)里就只有簡(jiǎn)單的賦值操作了，提高了效率藤滥。
對(duì)比選擇排序鳖粟，不能有效的利用元素本來(lái)的部分有序這個(gè)性質(zhì)，所以在基本有序的序列里拙绊，插入排序的效率十分高牺弹。
