這是一種對直接插入排序的一種改良，因為直接插入排序的第一步社裆，我們就能夠獲取到一個有序的集合了拙绊，對這個集合我們可以使用折半查找，查找下一個插入的位置泳秀。再說一下折半查找的實現(xiàn)原理标沪，但是折半查找有一個硬傷，要求待查找的集合是有序的嗜傅，所以我們在查找之前就需要先進行排序金句。比如我們要在1-8中找到3的話，使用折半查找
折半查找
代碼實現(xiàn)如下：
private static int Binary_Search(int num[],int key){
int startPos = 0;
int endPos = num.length - 1;
int middle;
// 當初始位置大于結(jié)束位置吕嘀，就是遍歷完畢的意思
while (startPos <= endPos) {
middle = (startPos + endPos)/2;
if (num[middle] == key) {
return middle;
}else if (num[middle] > key) {
//key可能在左邊违寞，startPos保持不變
endPos = middle - 1;
}else {
//key可能在右邊，endPos保持不變
startPos = middle + 1;
}
}
return -1;
}
上面的方法用于在一個有序的數(shù)組中查找元素key的位置偶房，接下來怎么在直接插入排序中加入折半查找呢趁曼？
private static int[] Insert_Binary_Sort(int[] num){
int temp;
//折半查找必備的三個要素
int low,high,middle;
for (int i = 1; i < num.length; i++) {
// 對于排序，我們只需要找出插入的位置就好了
//這個位置應該滿足|high- low|等于1棕洋，然后把值插入到他們之間
temp = num[i];//待插入記錄
//數(shù)組的0為開始位置挡闰，也是數(shù)組已排序的位置
low = 0;
//已排序數(shù)組的結(jié)束位置
high = i-1;
while (low <= high) {
middle = (low+high)/2;
if (num[middle] >temp) {
//中間的元素大于待插入值
high = middle -1;
}
else {
//中間的元素小于或等于待插入值
low = middle+1;
}
}
for (int j = i-1; j >= high + 1; j--) {
num[j+1] = num[j];//其余元素后移
}
num[high+1] = temp;//插入元素
}
return num;
}
折半插入排序比直接插入排序會快，但實際上它的時間復雜度還是O(n^2)，因為折半查找只是減少了待插入對象的比較次數(shù)而已摄悯，如果n較大的話赞季，那么折半插入排序的效率會比直接插入排序增益不少。
