前言： 折半插入排序（Binary Insertion Sort）是對(duì)直接插入排序算法的一種改進(jìn)。

插入排序思想介紹

折半插入排序與直接插入排序算法原理相同。只是，在向已排序的數(shù)據(jù)中插入數(shù)據(jù)時(shí)，采用來(lái)折半查找（二分查找）。先取已經(jīng)排序的序列的中間元素，與待插入的數(shù)據(jù)進(jìn)行比較，如果中間元素的值大于待插入的數(shù)據(jù)，那么待插入的數(shù)據(jù)屬于數(shù)組的前半部分，否則屬于后半部分。依次類(lèi)推，不斷縮小范圍，確定要插入的位置。

算法說(shuō)明：

待排序數(shù)據(jù)：2，1，6，7，4

取第一個(gè)元素作為有序表，剩余的元素作為無(wú)序表

　　   其中有序表：2；無(wú)序表：1，6，7，4

第一次比較，從無(wú)序表中取出第一個(gè)數(shù) 1，與中間值2比較，1<2，1插到2的前面，得到

　　   有序表：1，2；無(wú)序表：6，7，4

第二次比較，從無(wú)序表中取出第一個(gè)數(shù) 6，與中間值1比較，6>1，要放在1的后面，再與后半?yún)^(qū)（有序表：2）的中間值2比較，6>2，6插入到2的后面，得到

　　   有序表：1，2，6；無(wú)序表：7，4

第三次比較，從無(wú)序表中取出第一個(gè)數(shù) 7，與中間值2比較，7>2，7放在2后面，再與后半?yún)^(qū)（有序表：6）的中間值6比較，7>6，7放在6后面，得到

　　   有序表：1，2，6，7；無(wú)序表：4

第四次比較，從無(wú)序表中取出第一個(gè)數(shù) 4，與中間值2比較，4>2，4放在2后面，再與后半?yún)^(qū)（有序表:6,7）的中間值6比較，4<6，4放在6前面，最終得到：

　　   1，2，4，6，7

折半插入排序的代碼實(shí)現(xiàn)

1. private void binaryInsertSort(int arr[]){  

2.   

3.         int low = 0;  

4.         int high = 0;  

5.         int m = 0;// 中間位置  

6.         for(int i = 1; i < arr.length; i++){  

7.             low = 0;  

8.             high = i-1;  

9.             while(low <= high){  

10.                 m = (low+high)/2;  

11.                 if(arr[m] > arr[i])  

12.                     high = m - 1;  

13.                 else  

14.                     low = m + 1;  

15.             }  

16.             //統(tǒng)一移動(dòng)元素，將待排序元素插入到指定位置  

17.             temp = arr[i];  

18.             for(int j=i; j > high+1; j--){  

19.                 arr[j] = arr[j-1];  

20.             }  

21.             arr[high+1] = temp;  

22.         }          

23.     }  

總結(jié)

折半插入排序相對(duì)穩(wěn)定，相對(duì)于直接插入排序，減少了比較次數(shù)；但是相對(duì)直接插入排序，移動(dòng)次數(shù)不變。