前言

上一篇在聊時間復(fù)雜度和空間復(fù)雜度時，沒有按指定格式顯示(明明預(yù)覽的時候沒問題的)，強迫癥的我稍微優(yōu)化了一下重新發(fā)布，目的就是讓小伙伴看著舒服。

上次聊到的直接插入排序在比較有序數(shù)據(jù)和待插入數(shù)據(jù)時，是通過依次遍歷的方式進行比較，當(dāng)數(shù)據(jù)量比較大時，得考慮進一步優(yōu)化；折半插入排序就是通過減少有序數(shù)據(jù)與待插入數(shù)據(jù)的比較次數(shù)，從而提升效率。

正文

1. 先來熟悉一下折半查找

1.1 ?折半查找算法思想

折半查找又稱二分查找，僅適用于有序的順序表；

思想(假設(shè)順序表是升序的)：

• 首先將指定值與順序表中中間位置元素進行比較；

• 若相等，代表找到，則返回該元素的位置；

• 若不等，需繼續(xù)查找；

  若指定的值小于順序表中中間元素，則查找前半部分；

  若指定的值大于順序表中中間元素，則查找后半部分；

重復(fù)以上過程，直到找到元素為止；或者找完所有數(shù)據(jù)為止，即查找失敗；

1.2 折半查找實現(xiàn)及解析

算法代碼如下(在升序順序表中查數(shù)據(jù))

image-20210327174929319

執(zhí)行結(jié)果如下：

image-20210327175057909

解析查找步驟過程，如下：

圖中分別使用紅、綠、黃箭頭所指的數(shù)據(jù)分別高、中、低索引位，藍色為需要在順序表中查找的數(shù)。

能查到數(shù)據(jù)的步驟：

image-20210328000114746

上圖步驟說明：

• 第1步將low初始為0，high初始賦值為順序表中的元素個數(shù)減1，這里為5；當(dāng)循環(huán)進來時將mid賦值為(low+high)/2，因為mid為int類型，會取整，這里就得到mid為2；然后將索引位為2的數(shù)據(jù)66與需要查找的數(shù)據(jù)92進行比較，發(fā)現(xiàn)92大于66，需繼續(xù)在后半部分查找，所以將low的值改為mid+1,即為3；

• 第2步進入循環(huán)，繼續(xù)將mid的賦值為(low+high)/2，因為上一步low的值為3，high的值不變，還是為5，所以得出的mid值為4，然后將索引位為4的數(shù)據(jù)92與需要查找的數(shù)據(jù)92進行比較，兩者相等，代表已經(jīng)找到，返回當(dāng)時找到的位置mid。

查找失敗時的情況：

image-20210328000247255

上圖步驟說明：

• 第1步將low初始為0，high初始賦值為順序表中的元素個數(shù)減1，這里為5；當(dāng)循環(huán)進來時將mid賦值為(low+high)/2，因為mid為int類型，會取整，這里就得到mid為2；然后將索引位為2的數(shù)據(jù)66與需要查找的數(shù)據(jù)921進行比較，發(fā)現(xiàn)921大于66，需繼續(xù)在后半部分查找，所以將low的值改為mid+1,即為3；

• 第2步進入循環(huán)，繼續(xù)將mid的賦值為(low+high)/2，因為上一步low的值為3，high的值不變，還是為5，所以得出的mid值為4，然后將索引位為4的數(shù)據(jù)92與需要查找的數(shù)據(jù)921進行比較，發(fā)現(xiàn)921大于92，需繼續(xù)在后半部分查找，所以將low的值改為mid+1,即為5；

• 第3步進入循環(huán)，繼續(xù)將mid的賦值為(low+high)/2，因為上一步low的值為5，high的值不變，還是為5，所以得出的mid值為5(這里高、中、低都指向同一位置)，然后將索引位為5的數(shù)據(jù)100與需要查找的數(shù)據(jù)921進行比較，發(fā)現(xiàn)921大于100，需繼續(xù)在后半部分查找，所以將low的值改為mid+1,即為6；

• 第4步進入循環(huán)時，low在第3步時變?yōu)?，high還是沒變，依然是5，low大于high，不滿足循環(huán)條件，代表已經(jīng)查詢完成，但沒有查詢到數(shù)據(jù)，跳出循環(huán)，返回-1；

1.3 分析折半查找算法性能

時間復(fù)雜度

如果傳入的數(shù)據(jù)規(guī)模為n，即有n個元素；第一次在 n/2個元素中查找，第二次在n/(2²)個元素中查找，第三次在n/(2³)個元素中查找，假如經(jīng)過x次查找到元素，則得到時間復(fù)雜度為O(log₂n)；

空間復(fù)雜度

因為在查找過程中，用到了固定的幾個中間變量(low,mid,high)，所以算法過程中消耗的內(nèi)存是一個常量級別的，則空間復(fù)雜度為O(1)；

穩(wěn)定性

由于在算法過程中只是查找，不改變元素的位置，則折半查找算法是穩(wěn)定的。

綜上所述，插入排序的時間復(fù)雜度為O(log₂n)，空間復(fù)雜度為O(1)，是穩(wěn)定算法；

2. 搞明白折半插入排序

2.1 折半插入排序算法思想

折半插入排序是對直接插入排序的優(yōu)化，直接插入排序在比較過程中依次遍歷有序列表中的元素和待插入數(shù)據(jù)比較，而折半插入排序是將原來的依次遍歷有序列表換成折半查找算法，提升比較效率，找到合適位置之后，對應(yīng)的元素需要向后移位，然后將待插入元素插入到騰出的空位即可；重復(fù)到排序完成為止。

2.2 折半插入排序算法實現(xiàn)與解析

代碼實現(xiàn)(升序)：

image-20210329104257982

運行效果如下：

image-20210329104425770

步驟解析如圖：

image-20210329123521476

步驟說明：

圖中綠線框部分代表是已經(jīng)排好序的列表，箭頭指的元素是下一個待插入的元素，黃線框部分為剩下的無序元素。黃方塊為每次折半查找到的mid位置，綠方塊表示最后有序列表騰出的位置。

• 將原始數(shù)據(jù)array復(fù)制到新數(shù)組中arrayb中，這步的主要目的是后續(xù)不需要聲明額外臨時變量，也為了后續(xù)核心代碼實現(xiàn)邏輯簡單易懂，減少過多的判斷；

• 第1步將第一個元素作為有序列表(第一元素為2)，下一個待插入的元素為5，將5放入哨兵位置，即索引為0的位置；然后折半查找，初始low為1，high為第一次也為1；因為剛開始有序列表中只有一個元素，則找到就是2，與哨兵位的值5比較，2小于5，需要繼續(xù)在有序列表的后半部分查找，改變low為mid+1，此時為2，大于high，跳出循環(huán)；不需要移動位置，保持當(dāng)前位置不變。

• 第2步時，有序列表中的元素為2、5，下一個待插入的元素為6，將6放入哨兵位置，即索引為0的位置；然后折半查找：

  第2-1步 初始low為1，此時計算出high的值為2；根據(jù)low和high計算出mid為1(因為是mid是整數(shù)，所以3除以2，取整為1)，將mid位的值2與待插入元素6比較，2小于6，需要繼續(xù)在有序列表中的后半部分繼續(xù)查找，則改變low的值，為mid加1，得到low為2；

  第2-1步 上一步得到low為2，high的值仍然為2；根據(jù)low和high計算出mid為2，將mid位的值5與待插入元素6比較，5小于6，需要繼續(xù)在有序列表中的后半部分繼續(xù)查找，則改變low的值，為mid加1，得到low為3；不滿足循環(huán)條件，退出折半；不需要移動位置，保持當(dāng)前位置不變；

• 第3步時，有序列表中的元素為2、5、6，下一個待插入的元素為1，將1放入哨兵位置，即索引為0的位置；然后折半查找：

  第3-1步 初始low為1，此時計算出high的值為3；根據(jù)low和high計算出mid為2，將mid位的值5與待插入元素1比較，5大于1，需要繼續(xù)在有序列表中的前半部分繼續(xù)查找，則改變high的值，為mid減1，得到high為1；

  第3-2步 初始low為1，上一步計算出high的值為1；根據(jù)low和high計算出mid為1，將mid位的值2與待插入元素1比較，2大于1，需要繼續(xù)在有序列表中的前半部分繼續(xù)查找，則改變high的值，為mid減1，得到high為0；繼續(xù)循環(huán)是low大于high，不滿足條件，跳出循環(huán)；

  第3-3步 根據(jù)折半查找比較，得出合適位置為high+1，即需要將待插入元素插入到1位置，需要將2、5、6三個元素依次向后移位，騰出索引位1的位置，將待插入元素1插入到此索引位。

• 第4步時，有序列表中的元素為1、2、5、6，下一個待插入的元素為9，將9放入哨兵位置，即索引為0的位置；然后折半查找：

  第4-1步 初始low為1，此時計算出high的值為4；根據(jù)low和high計算出mid為2(因為是mid是整數(shù)，所以5除以2，取整為2)，將mid位的值2與待插入元素9比較，2小于9，需要繼續(xù)在有序列表中的后半部分繼續(xù)查找，則改變low的值，為mid+1，得到low為3；

  第4-2步 上一步計算出low為3，high的值仍然為4；根據(jù)low和high計算出mid為3(因為是mid是整數(shù)，所以7除以2，取整為3)，將mid位的值5與待插入元素9比較，5小于9，需要繼續(xù)在有序列表中的后半部分繼續(xù)查找，則改變low的值，為mid+1，得到low為4；

  第4-3步 上一步計算出low為4，high的值仍然為4；根據(jù)low和high計算出mid為4，將mid位的值6與待插入元素9比較，6小于9，需要繼續(xù)在有序列表中的后半部分繼續(xù)查找，則改變low的值，為mid+1，得到low為5；繼續(xù)循環(huán)是low大于high，不滿足條件，跳出循環(huán)；

• 第5步是，有序列表中的元素為1、2、5、6、9，下一個待插入的元素為3，將3放入哨兵位置，即索引為0的位置；然后折半查找：

  第5-1步 初始low為1，此時計算出high的值為5；根據(jù)low和high計算出mid為3，將mid位的值5與待插入元素3比較，5大于3，需要繼續(xù)在有序列表中的前半部分繼續(xù)查找，則改變high的值，為mid減1，得到high為2；

  第5-2步 初始low為1，上一步計算出high的值為2；根據(jù)low和high計算出mid為1(3除以2取整得1)，將mid位的值1與待插入元素3比較，1小于3，需要繼續(xù)在有序列表中的后半部分繼續(xù)查找，則改變low的值，為mid加1，得到low為2；

  第5-3步，上一步計算出low為2，第5-1步計算出high為2；根據(jù)low和high計算出mid為2，將mid位的值2與待插入元素3比較，2小于3，需要繼續(xù)在有序列表中的后半部分繼續(xù)查找，則改變low的值，為mid加1，得到low為3；繼續(xù)循環(huán)，不符合循環(huán)條件，循環(huán)終止

  第5-4步 根據(jù)折半查找比較，得出合適位置為high+1，即需要將待插入元素插入到3位置，需要將5、6、9三個元素依次向后移位，騰出索引位3的位置，將待插入元素3插入到此索引位。最終得到排序結(jié)果1、2、3 、5 、6 、9；

2.3 折半插入排序算法分析

時間復(fù)雜度

在算法過程中有兩層循環(huán)，第一層需要遍歷所有元素，則時間復(fù)雜度為O(n)；第二層循環(huán)中包含兩部分算法，第一步是通過折半算法找位置，時間復(fù)雜度在剛開始已經(jīng)分析，為O(log₂n)；第二步是找到位置之后需要騰出空位，需要將對應(yīng)元素移位，時間復(fù)雜度為O(n)；則整體算法的時間復(fù)雜度為外層循環(huán)的時間復(fù)雜度乘以內(nèi)層循環(huán)的時間復(fù)雜度，去掉系數(shù)和常數(shù)，取大的，得出結(jié)果為O(n²)；

空間復(fù)雜度

在算法核心部分只采用了固定的幾個中間變量(i,j,low,mid,high,arrayb[0])，所以算法過程中消耗的內(nèi)存是一個常量，則空間復(fù)雜度為O(1)；

穩(wěn)定性

由于在算法過程中采用折半算法找位置的，使用大于符號進行比較值，所以當(dāng)遇到相等數(shù)據(jù)時，位置不會受到改變，則折半插入算法是穩(wěn)定的。

綜上所述，折半插入排序的時間復(fù)雜度為O(n²)，空間復(fù)雜度為O(1)，是穩(wěn)定算法；

總結(jié)

這里說到兩種算法，折半查找(二分查找)算法，折半插入排序算法；最終關(guān)于插入排序算法的思想沒變，只是在比較有序列表時做了優(yōu)化；對于小數(shù)據(jù)量的排序，感覺不到優(yōu)化，當(dāng)數(shù)據(jù)量大時，比較效率就明顯提升啦；如果不明白的小伙伴調(diào)試代碼試試，再不行可以留言，有時間會及時回復(fù)。

感謝小伙伴的：點贊、收藏和評論，下期繼續(xù)~~~

一個被程序搞丑的帥小伙，關(guān)注"Code綜藝圈"，跟我一起學(xué)~~~

總結(jié)

以上是生活随笔為你收集整理的二分查找和折半插入排序一块说说-很合适~~~的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。