小米降噪藍(lán)牙耳機(jī)Necklace分享：聽(tīng)一首歌 讀懂一個(gè)故事
在今天下午的小米Civi 2新品發(fā)布會(huì)上，小米還帶來(lái)了一款新的降噪藍(lán)牙耳機(jī)Necklace，我們也在發(fā)布結(jié)束的第一時(shí)間給大家?guī)?lái)這款耳機(jī)的簡(jiǎn)單分享。現(xiàn)在大家能見(jiàn)到最多的藍(lán)牙耳機(jī)
先來(lái)回顧一下直接插入排序的算法思想，就是在前面已經(jīng)排好序的子序列中尋找一個(gè)待插入的位置，然后將待插入元素插入到該位置上。
其中尋找插入位置的過(guò)程我們是與每一個(gè)元素進(jìn)行比較，相當(dāng)于順序查找，我們知道順序查找的效率是比較低的，那么有沒(méi)有辦法能夠提高查找插入位置的效率呢？
很巧的是，前面的序列既然已經(jīng)是有序的了，我們何不采用折半查找來(lái)找出插入位置呢？折半查找的前提就是序列有序，采用折半查找法查找插入位置的插入排序算法，我們稱(chēng)其為折半插入排序。
折半插入算法非常簡(jiǎn)單，前提你得掌握直接插入排序和折半查找的算法，來(lái)看一個(gè)例子：
原序列的前四個(gè)元素已經(jīng)有序，則從i位置元素開(kā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位置開(kāi)始，到i - 1位置為止，將該范圍內(nèi)的所有元素后移，空開(kā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; //從第二個(gè)元素開(kāi)始插入排序 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(wú)關(guān)，僅依賴(lài)于對(duì)象個(gè)數(shù)。在插入第i個(gè)對(duì)象時(shí)，需要經(jīng)過(guò)「log2i」 + 1次關(guān)鍵碼比較才能確定插入位置。
本文鏈接：http://www.tebozhan.com/showinfo-26-12133-0.html【排序算法】-折半插入排序
聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。郵件：2376512515@qq.com
上一篇： 突破性能邊界，OpenSwoole 引領(lǐng) PHP 網(wǎng)絡(luò)編程新時(shí)代！
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請(qǐng)聯(lián)系：2376512515@qq.com 津ICP備18001702號(hào)
津公網(wǎng)安備 12010102000574號(hào)