上一節(jié)講了直接插入排序，本次講一個(gè)直接插入排序的進(jìn)階版——折半插入排序，二者的排序邏輯是一樣的，區(qū)別在于：
- 直接插入排序，每次需要插入的元素需要依次比較該元素之前的所有元素來確定其應(yīng)該插入前面已經(jīng)排好序的哪個(gè)位置。
- 折半插入排序，通過對(duì)前置排好序的列表進(jìn)行二分比較，先比較中間值，然后確定該元素在中間值的左/右，然后對(duì)應(yīng)在的范圍繼續(xù)進(jìn)行二分比較，直到確定插入到什么位置。
坐在巨人的肩膀上，感覺圖示也沒有必要了，折半插入就是直接選擇排序+二分法查找，直接上代碼整活兒~
public void binaryInsertionSort(int[] arrays, int start, int end) {
if (start == end) {
return;
}
for (int i = start + 1; i <= end; i++) {
// [start, i-1]已經(jīng)排好序，只要將i插入其中即可
int low = start;
int high = i - 1;
while (low <= high) {
int middle = (low + high) / 2;
if (arrays[middle] > arrays[i]) {
high = middle - 1;
} else {
low = middle + 1;
}
}
int val = arrays[i];
// i位置的值應(yīng)該放在high+1的位置，開始移動(dòng)
for (int j = i; j > high + 1; j--) {
arrays[j] = arrays[j - 1];
}
arrays[high + 1] = val;
}
}
在寫代碼的時(shí)候呢，其實(shí)我發(fā)現(xiàn)有兩個(gè)地方容易寫錯(cuò)（也可能是本人水平有限），在此說明一下，填坑。。。
- 中間值比array[i]大，即找前半部分，否則找后半部分------
當(dāng)中間值確定的已經(jīng)到了low=high時(shí)，即中間值沒有前后部分了
只有這一個(gè)元素了，也就是快到了跳出while的時(shí)候，即low>high
此時(shí)有個(gè)糾結(jié)的點(diǎn)是array[i]應(yīng)該插入到low的位置還是high的位置?
此時(shí)我們進(jìn)行分類討論（此時(shí)不妨設(shè)置對(duì)應(yīng)索引下標(biāo)low=high=x）：
① 若arrays[x] > arrays[i]，此時(shí)應(yīng)查找x的左半部分，此時(shí)：
-- low = x, high = x - 1; 跳出while,
-- 此時(shí)arrays[i]應(yīng)該放到x位置，將原[x, i-1]位置的數(shù)據(jù)“擠”到[x+1, i]
② 若arrays[x] <= arrays[i]，此時(shí)應(yīng)查找x的右半部分，此時(shí)：
-- low = x + 1, high = x ; 跳出while,
-- 此時(shí)arrays[i]應(yīng)該放到x位置，將原[x+1, i-1]位置的數(shù)據(jù)“擠”到[x+2, i]
綜上，當(dāng)跳出循環(huán)的時(shí)候，其實(shí)就是將arrays[i]放到low的位置(也就是high+1)，然后將[low, i-1]位置數(shù)據(jù)放置到[low+1, i]
上面所述的一個(gè)究竟將arrays[i]放到哪個(gè)位置的問題就迎刃而解了，有的時(shí)候腦子思考不清晰，就可以直接舉例試一下的方式來解決一下，不一定非得推導(dǎo)出什么公式、定理，我們又不是什么偉大優(yōu)秀的數(shù)學(xué)天才，數(shù)形結(jié)合，分類討論，能解決問題就行。
其次，在做相應(yīng)位置的賦值的時(shí)候我也犯迷糊了，連翻兩車，記錄一下。。。
正確代碼:
int val = arrays[i];
// i位置的值應(yīng)該放在high+1的位置，開始移動(dòng)
for (int j = i; j > high + 1; j--) {
arrays[j] = arrays[j - 1];
}
arrays[high + 1] = val;
第一車：
// i位置的值應(yīng)該放在high+1的位置，開始移動(dòng)
for (int j = high+1; j < i; j++) {
arrays[j+1] = arrays[j];
}
arrays[high + 1] = val;
這車翻的徹底，直接依次將[high+1, i-1]的值賦值到[high+2, i]，然后最后導(dǎo)致我打印排序結(jié)果出來很多相同的值，稍微看了一下，還是自己犯蠢了：
arrays[i+2] = arrays[i+1];
arrays[i+3] = arrays[i+2];
尷尬三連：i+2的值已經(jīng)被賦值為了i+1的值了，那i+2的值給i+3不還是歸根到底講i+1的值給覆蓋過去了。。。尷尬癌晚期
第一車翻徹底后，醒悟了翻了第二車：
// i位置的值應(yīng)該放在high+1的位置，開始移動(dòng)
for (int j = i; j > high + 1; j--) {
arrays[j] = arrays[j - 1];
}
arrays[high + 1] = val;
這下我倒著移動(dòng)賦值:
先將i-1位置的值賦值到i位置
先將i-2位置的值賦值到i-1位置
以此類推，結(jié)束賦值，這樣倒序賦值就不會(huì)出現(xiàn)覆蓋的情況
最后還是出現(xiàn)了類似第一車的結(jié)果，
仔細(xì)觀察正確代碼和第二車的差異，不難發(fā)現(xiàn)，其實(shí)就是將i位置原來的值取出來罷了，因?yàn)樵谝苿?dòng)賦值時(shí)會(huì)將i位置值覆蓋為i-1的值，所以最終high+1位置并不是賦值為了原i位置的值，而是原i-1位置的值。
究其根本，是因?yàn)閕位置值被i-1位置覆蓋了，需要提前使用中間值存儲(chǔ)，否則i位置原本的值就被覆蓋掉了。。。
原本我覺得此算法同直接插入排序差不多，不就是比較通過二分法進(jìn)行快速區(qū)分范圍確定插入元素應(yīng)在已排序的前置數(shù)組中的位置，然后將被"擠"出去的列表塊一同往后移動(dòng)一個(gè)位置，但是寫出來還是翻車了
最終也是印證了一句話：嘴強(qiáng)王者沒卵用，紙上得來終覺淺，該擼代碼還得擼！
