相比較直接插入排序，二分插入的優(yōu)勢(shì)在于：對(duì)待排序數(shù)所應(yīng)該插入的位置的計(jì)算是通過二分法來尋找的，這種二分查找的時(shí)間復(fù)雜度為o(logn)；而直接插入是依次尋找位置的，時(shí)間復(fù)雜度可看作o(n)。
故二分插入排序是一種優(yōu)化過的插入排序。

?完整二分插入升序代碼如下：

#include<iostream>void insertSort(int* arr, int num);int main(){int a[20] = { 3, 2, 4, 6, 7, 5, 18, 9, 0, 1,16, 8, 20, 33, 28, 64, 19, 31, 30, 25 };for (int i = 0; i < 20; i++){std::cout << a[i] << " ";}std::cout << '\n';insertSort(a, 20);for (int i = 0; i < 20; i++){std::cout << a[i] << " ";}return 0;}//上面的么得啥用。。。void insertSort(int* arr, int num){int temp, i, j;//temp保存每一次的新數(shù)，因?yàn)閿?shù)組元素的移動(dòng)會(huì)覆蓋掉新數(shù)int low, mid, high;//設(shè)置區(qū)間的兩端和中間的下標(biāo)for (i = 1; i < num; ++i)//所謂外循環(huán)，每次放一個(gè)新數(shù)進(jìn)去參與排序{if (arr[i] < arr[i - 1])//若下標(biāo)i以前的數(shù)不是有序的，執(zhí)行if語句內(nèi)容//此時(shí)的無序指的是下標(biāo)0~i-1是有序的，需要將下標(biāo)i中的數(shù)重新插入，使其變得有序{temp = arr[i];//保存每次的新數(shù)low = 0;high = i - 1;//每一輪第一次初始化low和highwhile (low <= high){mid = (low + high) / 2;if (temp < arr[mid])high = mid - 1;elselow = mid + 1;}//***while結(jié)束后，下標(biāo)high+1處為待插入的位置。***for (j = i - 1; j > high; j--)arr[j + 1] = arr[j];arr[high + 1] = temp;}}}

其中排序函數(shù)insertSort中的while循環(huán)判定條件為low<=high，當(dāng)循環(huán)結(jié)束后，high+1處為待排序數(shù)該插入的位置，然后我們?cè)谶M(jìn)行后續(xù)的數(shù)組移動(dòng)，以及插入新數(shù)，至此一輪循環(huán)結(jié)束。（其實(shí)low始終等于high+1，等于待排序數(shù)該插入的位置，故也可以用low來表示插入位置。下面這樣也是可以的

for (j = i - 1; j >=low; j--)arr[j + 1] = arr[j]; arr[low] = temp;

)

---

二分插入排序的時(shí)間復(fù)雜度為o(),空間復(fù)雜度為o(1)。?

二分插入排序是穩(wěn)定的，如果你想讓它穩(wěn)定的話。

如果是進(jìn)行升序排序的話，下面幾行代碼不能進(jìn)行更改，因?yàn)橐欢ㄒ扰衪emp小于arr[mid]，這樣就將大于和等于的情況放在else語句里頭，從而保證了當(dāng)temp等于arr[mid]時(shí)排序的穩(wěn)定性。

if (temp < arr[mid])high = mid - 1; elselow = mid + 1;

不能寫成下面這樣

if (temp > arr[mid])low = mid + 1; elsehigh = mid - 1;

---

附上降序排序的穩(wěn)定算法，如下

void insertSort(int* arr, int num){int temp, i, j;int low, mid, high;for (i = 1; i < num; ++i){if (arr[i] > arr[i - 1])//有所改變{temp = arr[i];low = 0;high = i - 1;while (low <= high){mid = (low + high) / 2;if (temp > arr[mid])//有所改變high = mid - 1;elselow = mid + 1;}for (j = i - 1; j >high; j--)arr[j + 1] = arr[j];arr[high+1] = temp;}}}

?

總結(jié)

以上是生活随笔為你收集整理的插入排序之——二分（折半）插入排序（c/c++）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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