二分查找和折半插入排序一塊說說-很合適~~~

2021 年 3 月 31 日
筆記
數據結構及演算法

前言

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

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

正文

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

1.1 折半查找演算法思想

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

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

首先將指定值與順序表中中間位置元素進行比較；
若相等，代表找到，則返回該元素的位置；
若不等，需繼續查找；

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

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

重複以上過程，直到找到元素為止；或者找完所有數據為止，即查找失敗；

1.2 折半查找實現及解析

演算法程式碼如下(在升序順序表中查數據)

執行結果如下：

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

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

能查到數據的步驟：

上圖步驟說明：

第1步將low初始為0，high初始賦值為順序表中的元素個數減1，這裡為5；當循環進來時將mid賦值為(low+high)/2，因為mid為int類型，會取整，這裡就得到mid為2；然後將索引位為2的數據66與需要查找的數據92進行比較，發現92大於66，需繼續在後半部分查找，所以將low的值改為mid+1,即為3；
第2步進入循環，繼續將mid的賦值為(low+high)/2，因為上一步low的值為3，high的值不變，還是為5，所以得出的mid值為4，然後將索引位為4的數據92與需要查找的數據92進行比較，兩者相等，代表已經找到，返回當時找到的位置mid。

查找失敗時的情況：

上圖步驟說明：

第1步將low初始為0，high初始賦值為順序表中的元素個數減1，這裡為5；當循環進來時將mid賦值為(low+high)/2，因為mid為int類型，會取整，這裡就得到mid為2；然後將索引位為2的數據66與需要查找的數據921進行比較，發現921大於66，需繼續在後半部分查找，所以將low的值改為mid+1,即為3；
第2步進入循環，繼續將mid的賦值為(low+high)/2，因為上一步low的值為3，high的值不變，還是為5，所以得出的mid值為4，然後將索引位為4的數據92與需要查找的數據921進行比較，發現921大於92，需繼續在後半部分查找，所以將low的值改為mid+1,即為5；
第3步進入循環，繼續將mid的賦值為(low+high)/2，因為上一步low的值為5，high的值不變，還是為5，所以得出的mid值為5(這裡高、中、低都指向同一位置)，然後將索引位為5的數據100與需要查找的數據921進行比較，發現921大於100，需繼續在後半部分查找，所以將low的值改為mid+1,即為6；
第4步進入循環時，low在第3步時變為6，high還是沒變，依然是5，low大於high，不滿足循環條件，代表已經查詢完成，但沒有查詢到數據，跳出循環，返回-1；

1.3 分析折半查找演算法性能

時間複雜度

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

空間複雜度

因為在查找過程中，用到了固定的幾個中間變數(low,mid,high)，所以演算法過程中消耗的記憶體是一個常量級別的，則空間複雜度為O(1)；

穩定性

由於在演算法過程中只是查找，不改變元素的位置，則折半查找演算法是穩定的。

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

2. 搞明白折半插入排序

2.1 折半插入排序演算法思想

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

2.2 折半插入排序演算法實現與解析

程式碼實現(升序)：

運行效果如下：

步驟解析如圖：

步驟說明：

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

將原始數據array複製到新數組中arrayb中，這步的主要目的是後續不需要聲明額外臨時變數，也為了後續核心程式碼實現邏輯簡單易懂，減少過多的判斷；
第1步將第一個元素作為有序列表(第一元素為2)，下一個待插入的元素為5，將5放入哨兵位置，即索引為0的位置；然後折半查找，初始low為1，high為第一次也為1；因為剛開始有序列表中只有一個元素，則找到就是2，與哨兵位的值5比較，2小於5，需要繼續在有序列表的後半部分查找，改變low為mid+1，此時為2，大於high，跳出循環；不需要移動位置，保持當前位置不變。
第2步時，有序列表中的元素為2、5，下一個待插入的元素為6，將6放入哨兵位置，即索引為0的位置；然後折半查找：

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

第2-1步上一步得到low為2，high的值仍然為2；根據low和high計算出mid為2，將mid位的值5與待插入元素6比較，5小於6，需要繼續在有序列表中的後半部分繼續查找，則改變low的值，為mid加1，得到low為3；不滿足循環條件，退出折半；不需要移動位置，保持當前位置不變；
第3步時，有序列表中的元素為2、5、6，下一個待插入的元素為1，將1放入哨兵位置，即索引為0的位置；然後折半查找：

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

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

第3-3步根據折半查找比較，得出合適位置為high+1，即需要將待插入元素插入到1位置，需要將2、5、6三個元素依次向後移位，騰出索引位1的位置，將待插入元素1插入到此索引位。
第4步時，有序列表中的元素為1、2、5、6，下一個待插入的元素為9，將9放入哨兵位置，即索引為0的位置；然後折半查找：

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

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

第4-3步上一步計算出low為4，high的值仍然為4；根據low和high計算出mid為4，將mid位的值6與待插入元素9比較，6小於9，需要繼續在有序列表中的後半部分繼續查找，則改變low的值，為mid+1，得到low為5；繼續循環是low大於high，不滿足條件，跳出循環；
第5步是，有序列表中的元素為1、2、5、6、9，下一個待插入的元素為3，將3放入哨兵位置，即索引為0的位置；然後折半查找：

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

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

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

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

2.3 折半插入排序演算法分析

時間複雜度

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

空間複雜度

在演算法核心部分只採用了固定的幾個中間變數(i,j,low,mid,high,arrayb[0])，所以演算法過程中消耗的記憶體是一個常量，則空間複雜度為O(1)；

穩定性

由於在演算法過程中採用折半演算法找位置的，使用大於符號進行比較值，所以當遇到相等數據時，位置不會受到改變，則折半插入演算法是穩定的。

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

總結

這裡說到兩種演算法，折半查找(二分查找)演算法，折半插入排序演算法；最終關於插入排序演算法的思想沒變，只是在比較有序列表時做了優化；對於小數據量的排序，感覺不到優化，當數據量大時，比較效率就明顯提升啦；如果不明白的小夥伴調試程式碼試試，再不行可以留言，有時間會及時回復。

感謝小夥伴的：點贊、收藏和評論，下期繼續~~~

一個被程式搞丑的帥小伙，關注"Code綜藝圈"，跟我一起學~~~

Tags: 數據結構及演算法