排序算法總結(jié)之折半插入排序
來源：程序員人生 發(fā)布時間：2014-09-15 03:44:10 閱讀次數(shù)：3251次
基本思想
折半插入排序是對直接插入排序的簡單改進(jìn)，對于直接插入排序而言，當(dāng)?shù)趇-1趟需要將第i個元素插入前面的0~i-1個元素序列中時，總是需要從i-1個元素開始，逐個比較每個元素，直到找到它的位置。這顯然沒有利用前面0~i-1個元素已經(jīng)有序這個特點(diǎn)，而折半插入排序則改進(jìn)了這一點(diǎn)。
對于折半插入排序而言，當(dāng)需要插入第i個元素時，它不會逐個進(jìn)行比較每個元素，而是：
（1）計算0~i-1索引的中間點(diǎn)，也就是用i索引處的元素和(0+i-1)/2索引處的元素進(jìn)行比較，如果i索引處的元素值大，就直接在(0+i-1)/2~i-1半個范圍內(nèi)進(jìn)行搜索；反之在0~(0+i-1)/2半個范圍內(nèi)搜索，這就是所謂的折半；
（2）在半個范圍內(nèi)搜索時，按照（1）的方法不斷地進(jìn)行折半搜索，這樣就可以將搜索范圍縮小到1/2、1/4、1/8…，從而快速的確定插入位置；
Java實(shí)現(xiàn)代碼
package com.liuhao.sort;
import java.util.Arrays;
public class BinaryInsertSort {
public static void binaryInsertSort(DataWrap[] data){
int arrayLength = data.length;
for(int i=1; i<arrayLength; i++){
DataWrap tmp = data[i];
int low = 0;
int high = i-1;
// 不斷折半，尋找合適的插入位置
while(low <= high){
int mid = (low + high) / 2;
if(tmp.compareTo(data[mid]) > 0){
low = mid + 1;
}
else{
high = mid - 1;
}
}
// 依次后移
for(int j=i; j>low ; j--){
data[j] = data[j-1];
}
data[low] = tmp;
System.out.println(Arrays.toString(data));
}
}
public static void main(String[] args) {
DataWrap[] data = {
new DataWrap(21, "")
,new DataWrap(30, "")
,new DataWrap(49, "")
,new DataWrap(30, "*")
,new DataWrap(16, "")
,new DataWrap(9, "") };
System.out.println("排序之前：" + Arrays.toString(data));
binaryInsertSort(data);
System.out.println("排序之后：" + Arrays.toString(data));
}
}
算法分析
折半插入排序減少了關(guān)鍵字的比較次數(shù)，但是記錄的移動次數(shù)不變，其時間復(fù)雜度與直接插入排序相同。
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈
