一、什么是二分插入排序？

二分法插入排序，簡稱二分排序，是在插入第i個元素時，對前面的0～i-1元素進行折半，先跟他們中間的那個元素比，如果小，則對前半再進行折半，否則對后半進行折半，直到left<right，然后再把第i個元素前1位與目標位置之間的所有元素后移，再把第i個元素放在目標位置上。（出自百度搜素）。

二、二分查找

想要徹底弄明白二分插入排序，就首先要知道什么是二分查找法。

首先我們先來說說什么是二分查找法，說白了就是折中查找。什么是折中查找呢?

如圖：

折中查找就是在一個數(shù)組查找到一個元素的位置（記住所查找的元素必須是一個升序的數(shù)組)。

圖中第一步定義的min 和 max 分別對應(yīng)的是下標最小值和小標最大值，num所對應(yīng)的是min+max的折中取整值。

第二步拿所要查找的元素與數(shù)組中下標為num的元素進行大小比較。當查找元素 > a[num]時，那么min = num + 1，為什么min的值會變成num + 1？因為通過比較可知查找元素是在a[num]元素的右邊，所以min就要更新為num + 1，且max值不變。當查找元素 < a[num]時，max 的變化原理與min值變化原理相同。當查找元素 == a[num]時，就說明你所要查找的元素已經(jīng)找到，可以將其打印出來，并停止循環(huán)。

通過while循環(huán)第二步，其中num的值需要放在循環(huán)中，循環(huán)停止條件是在min > max時停止循環(huán)。

第三步當循環(huán)停止時，且min > max時，就說明在數(shù)組中是找不到你要查找的數(shù)字。

while(min <= max){int num1 = (min+max) / 2;if(num < i[num1]){max = num1-1; }else if(num > i[num1]){min = num1+1;}else{printf("%d\n",i[num1]);break;}}if(min > max){printf("查詢不到這個數(shù)\n");}

三、二分插入排序過程

了解完二分查找后，我們就來說說什么是二分插入。想知道二分插入排序，我建議是可以先去了解一下什么是插入排序，兩者的區(qū)別在于怎樣找到插入的位置。

插入排序的插入位置是可以自己設(shè)置的，數(shù)組中想插入到哪就插入到哪，前提是這個數(shù)組要大，對升序降序沒有要求。

而二分插入排序的插入位置是通過二分查找找到的，前提是這個數(shù)組也要夠大，而且這個數(shù)組必須是一個升序的數(shù)組才能進行二分插入排序。

通過二分查找我們可知當min > max時是說明這個數(shù)組中是沒有你要查找的數(shù)字，而在二分插入排序中當 min > max時，就是找到了插入的位置，插入的位置的下標等于min，且在二分查找的過程中就不需要寫 = 的情況了

例：定義一個升序的數(shù)組 a[8] = {11，24，35，46，59，67，78}。其中我要向數(shù)組插入47。

11，24，35，46，59，67，78

通過改良二分查找，可以得到 最終跳出循環(huán)后min = 4，那么47最終插入的位置就為下標 = 4的位置，原先插入位置的元素和后面的元素全部向后移動一位。

所以最終的結(jié)果{11，24，35，46，47，59，67，78}

四、代碼完整過程

#include <stdio.h>int arr_num_lp(int *p,int n,int m)//查找插入位置 {int min = 0;int max = n - 1;int temp = m;while(min <= max){int num = (min + max) / 2;if(temp < p[num]){max = num - 1;}else{min = num + 1;}}return min; }void arr_ist_sort(int *p,int n,int m)//元素后移 {int i = 0;for(i = 7;i >= m;i--){p[i] = p[i] ^ p[i + 1];p[i + 1] = p[i] ^ p[i + 1];p[i] = p[i] ^ p[i + 1];}p[m] = n; }void arr_out(int a[9])//將數(shù)組輸出 {int i = 0;for(i = 0;i < 9;i++){printf("%d ",a[i]);}printf("\n"); }int main() {int a[9] = {0};int i = 0;printf("請輸入一個遞增的數(shù)組\n");for(i = 0;i < 8;i++){scanf("%d",&a[i]);}printf("請輸入你要插入的數(shù)字：\n");int j = 0;scanf("%d",&j);int min = arr_num_lp(a,9,j);//調(diào)用查找位置函數(shù)arr_ist_sort(a,j,min);//調(diào)用位置交換元素arr_out(a);//調(diào)用數(shù)組輸出函數(shù)return 0; }

總結(jié)

以上是生活随笔為你收集整理的二分插入排序（c语言）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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