現在我來簡單敘述一下二分法排序的思想，在插入第i個元素時，對前面的0～i-1元素進行折半，先跟他們中間的那個元素比，如果小，則對前半再進行折半，否則對后半進行折半，直到left>right，然后再把第i個元素前1位與目標位置之間的所有元素后移，再把第i個元素放在目標位置上。

實際上我們看到，這是用一種方式來查找最合適的數值應該插入的位置。這個和快速排序有些相像之處但是也不完全相同。它實際上也是通過折半查找找到每個元素應該存放的位置。

下面我將根據我的代碼來具體解釋一下。

/*** 二分法排序<br>* 根據排序原則，每次我們都是在一個有序序列中插入一個新的數字<br>* 那么我們可以將這個有序序列進行二分。<br>* 左游標left為0，右游標right為i-1(i是這個數字在原數組中的位置)<br>* middle初始為。<br>* 當left<=right時<br>* middle是left和right的中值。<br>* 我們作如下操作。如果array[i]的值比array[middle]值大。<br>* 那么我們就移動左游標令值為middle+1<br>* 負責就移動右游標為middle-1<br>* 移動完成后,我們需要將i-1到left之間的值進行依次向后移動給array[i]空出一個位置然后將array[i]插入* <p style="color:red">時間復雜度n</p>*/ public int[] binaryInsertSort(int[] array){for(int i = 0;i<array.length;i++){int temp = array[i];//待插入到前面有序序列的值int left = 0;//有序序列的左側int right = i-1;//有序序列的右側int middle = 0;//有序序列的中間while(left <= right){middle = (left + right)/2;//賦值if(temp<array[middle]){right = middle-1;}else{left = middle + 1;}}for(int j = i-1;j>=left;j--){//從i-1到left依次向后移動一位,等待temp值插入array[j+1] = array[j];}if(left != i ){array[left] = temp;}}return array; }

首先我們看到，我們需要left 和 right 的值。將left的值設置為0，right的值設置為查找的位置的前一個（i-1）。

首先確定中間值middle = (left+right)/2.如果這個值比目標值大，則從右側開始去查找。令left = middle+1;

否則令right = middle -1 ; 這個地方需要說明一下， i是不斷遞增的，所以每次插入的新數字都是在一個已經排好序列的數組中進行的。如果查到合適的位置，就令然后再把第i個元素前1位與目標位置（left）之間的所有元素后移，再把第i個元素放在目標位置上。

if(left != i ){array[left] = temp;}這個是為了讓目標位置的值賦值為temp（目標值）

總結

以上是生活随笔為你收集整理的算法排序----二分排序法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。