基本思想

先來回顧一下直接插入排序的算法思想，就是在前面已經排好序的子序列中尋找一個待插入的位置，然后將待插入元素插入到該位置上。X6U28資訊網——每日最新資訊28at.com

其中尋找插入位置的過程我們是與每一個元素進行比較，相當于順序查找，我們知道順序查找的效率是比較低的，那么有沒有辦法能夠提高查找插入位置的效率呢？X6U28資訊網——每日最新資訊28at.com

很巧的是，前面的序列既然已經是有序的了，我們何不采用折半查找來找出插入位置呢？折半查找的前提就是序列有序，采用折半查找法查找插入位置的插入排序算法，我們稱其為折半插入排序。X6U28資訊網——每日最新資訊28at.com

圖解排序過程

折半插入算法非常簡單，前提你得掌握直接插入排序和折半查找的算法，來看一個例子：X6U28資訊網——每日最新資訊28at.com

X6U28資訊網——每日最新資訊28at.com

原序列的前四個元素已經有序，則從i位置元素開始進行插入排序，先將i位置元素存入下標0作為哨兵，然后在子序列中尋找待插入位置。X6U28資訊網——每日最新資訊28at.com

這時我們可以采用折半查找法進行查找，定義三個變量low、high和mid，初始low = 1，high = i -1，則mid為2。X6U28資訊網——每日最新資訊28at.com

讓哨兵位置元素值與mid位置元素值比較，7大于5，所以插入位置應該在右半區，讓low = mid + 1，high不變，繼續折半查找：X6U28資訊網——每日最新資訊28at.com

X6U28資訊網——每日最新資訊28at.com

此時high大于low，查找結束，則插入位置即為high + 1，這些都是折半查找的內容，這里不贅述。X6U28資訊網——每日最新資訊28at.com

找到了插入位置為high + 1，可不能直接將待插入元素值存入high + 1位置，這樣會覆蓋原先的元素值，而應該從high + 1位置開始，到i - 1位置為止，將該范圍內的所有元素后移，空開high + 1位置，最后將哨兵位置元素插入到high + 1位置即可。X6U28資訊網——每日最新資訊28at.com

代碼實現

先構建待排序序列：X6U28資訊網——每日最新資訊28at.com

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;    }}

折半插入排序算法如下：X6U28資訊網——每日最新資訊28at.com

public class Main {    public static void BInsertSort(SSTable t) {        int i, j, low, high, mid;        //從第二個元素開始插入排序        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);    }}

性能分析

可以肯定的是，折半插入排序的效率是要高于直接插入排序的，它所需要的關鍵碼比較次數與待排序對象序列的初始排列無關，僅依賴于對象個數。在插入第i個對象時，需要經過「log2i」 + 1次關鍵碼比較才能確定插入位置。X6U28資訊網——每日最新資訊28at.com

本文鏈接：http://www.www897cc.com/showinfo-26-12133-0.html【排序算法】-折半插入排序

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com

上一篇： 突破性能邊界，OpenSwoole 引領 PHP 網絡編程新時代！

下一篇： 推薦八個上熱搜的GitHub開源項目