【排序算法】-折半插入排序
基本思想
先來回顧一下直接插入排序的算法思想，就是在前面已經(jīng)排好序的子序列中尋找一個(gè)待插入的位置，然后將待插入元素插入到該位置上。
其中尋找插入位置的過程我們是與每一個(gè)元素進(jìn)行比較，相當(dāng)于順序查找，我們知道順序查找的效率是比較低的，那么有沒有辦法能夠提高查找插入位置的效率呢？
很巧的是，前面的序列既然已經(jīng)是有序的了，我們何不采用折半查找來找出插入位置呢？折半查找的前提就是序列有序，采用折半查找法查找插入位置的插入排序算法，我們稱其為折半插入排序。
圖解排序過程
折半插入算法非常簡(jiǎn)單，前提你得掌握直接插入排序和折半查找的算法，來看一個(gè)例子：
原序列的前四個(gè)元素已經(jīng)有序，則從i位置元素開始進(jìn)行插入排序，先將i位置元素存入下標(biāo)0作為哨兵，然后在子序列中尋找待插入位置。
這時(shí)我們可以采用折半查找法進(jìn)行查找，定義三個(gè)變量low、high和mid，初始low = 1，high = i -1，則mid為2。
讓哨兵位置元素值與mid位置元素值比較，7大于5，所以插入位置應(yīng)該在右半?yún)^(qū)，讓low = mid + 1，high不變，繼續(xù)折半查找：
7小于10，則插入位置應(yīng)該在左半?yún)^(qū)，讓high = mid - 1，low不變：
此時(shí)high大于low，查找結(jié)束，則插入位置即為high + 1，這些都是折半查找的內(nèi)容，這里不贅述。
找到了插入位置為high + 1，可不能直接將待插入元素值存入high + 1位置，這樣會(huì)覆蓋原先的元素值，而應(yīng)該從high + 1位置開始，到i - 1位置為止，將該范圍內(nèi)的所有元素后移，空開high + 1位置，最后將哨兵位置元素插入到high + 1位置即可。
代碼實(shí)現(xiàn)
先構(gòu)建待排序序列：
public class ElemType {
int key;
}
public class SSTable {
ElemType[] n;
int length;
public SSTable() {
this.length = 11;
this.n = new ElemType[this.length + 1];
for (int i = 1; i <= this.length; i++) {
this.n[i] = new ElemType();
}
this.n[1].key = 3;
this.n[2].key = 5;
this.n[3].key = 10;
this.n[4].key = 16;
this.n[5].key = 7;
this.n[6].key = 32;
this.n[7].key = 83;
this.n[8].key = 23;
this.n[9].key = 54;
this.n[10].key = 29;
this.n[11].key = 96;
}
}折半插入排序算法如下：
public class Main {
public static void BInsertSort(SSTable t) {
int i, j, low, high, mid;
//從第二個(gè)元素開始插入排序
for (i = 2; i <= t.length; ++i) {
//將待插入元素存入哨兵位置
ElemType temp = t.n[i];
//為low和high賦初值
low = 1;
high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (temp.key < t.n[mid].key) {
high = mid - 1;
} else {
low = mid + 1;
}
}
//將high + 1到i - 1的元素后移
for (j = i - 1; j >= high + 1; --j) {
t.n[j + 1] = t.n[j];
}
//將哨兵位置元素插入j + 1位置
t.n[j + 1] = temp;
}
}
public static void main(String[] args) {
SSTable st = new SSTable();
BInsertSort(st);
}
}性能分析
可以肯定的是，折半插入排序的效率是要高于直接插入排序的，它所需要的關(guān)鍵碼比較次數(shù)與待排序?qū)ο笮蛄械某跏寂帕袩o關(guān)，僅依賴于對(duì)象個(gè)數(shù)。在插入第i個(gè)對(duì)象時(shí)，需要經(jīng)過「log2i」 + 1次關(guān)鍵碼比較才能確定插入位置。
