小米官宣：2023年上半年出貨量中國第一！
今日早間，小米電視官方微博帶來消息，稱2023年小米電視上半年出貨量達到了中國第一，同時還表示小米電視的巨屏風暴即將開始。“公布一個好消息2023年#小米電視上半年出貨量中國
先來回顧一下直接插入排序的算法思想，就是在前面已經(jīng)排好序的子序列中尋找一個待插入的位置，然后將待插入元素插入到該位置上。
其中尋找插入位置的過程我們是與每一個元素進行比較，相當于順序查找，我們知道順序查找的效率是比較低的，那么有沒有辦法能夠提高查找插入位置的效率呢？
很巧的是，前面的序列既然已經(jīng)是有序的了，我們何不采用折半查找來找出插入位置呢？折半查找的前提就是序列有序，采用折半查找法查找插入位置的插入排序算法，我們稱其為折半插入排序。
折半插入算法非常簡單，前提你得掌握直接插入排序和折半查找的算法，來看一個例子：
原序列的前四個元素已經(jīng)有序，則從i位置元素開始進行插入排序，先將i位置元素存入下標0作為哨兵，然后在子序列中尋找待插入位置。
這時我們可以采用折半查找法進行查找，定義三個變量low、high和mid，初始low = 1，high = i -1，則mid為2。
讓哨兵位置元素值與mid位置元素值比較，7大于5，所以插入位置應(yīng)該在右半?yún)^(qū)，讓low = mid + 1，high不變，繼續(xù)折半查找：
此時high大于low，查找結(jié)束，則插入位置即為high + 1，這些都是折半查找的內(nèi)容，這里不贅述。
找到了插入位置為high + 1，可不能直接將待插入元素值存入high + 1位置，這樣會覆蓋原先的元素值，而應(yīng)該從high + 1位置開始，到i - 1位置為止，將該范圍內(nèi)的所有元素后移，空開high + 1位置，最后將哨兵位置元素插入到high + 1位置即可。
先構(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; //從第二個元素開始插入排序 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)，僅依賴于對象個數(shù)。在插入第i個對象時，需要經(jīng)過「log2i」 + 1次關(guān)鍵碼比較才能確定插入位置。
本文鏈接：http://www.tebozhan.com/showinfo-26-12133-0.html【排序算法】-折半插入排序
聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
上一篇： 突破性能邊界，OpenSwoole 引領(lǐng) PHP 網(wǎng)絡(luò)編程新時代！
下一篇： 推薦八個上熱搜的GitHub開源項目
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請聯(lián)系：2376512515@qq.com 津ICP備18001702號
津公網(wǎng)安備 12010102000574號