折半插入排序

   如果在最複雜的情況下，所要排序的整個數列是逆序的，當第 i-1 趟需要将 第 i 個元素插入前面的 0~ i -1 個元素的序列當中的時候，它總是會從第 i -1 個元素開始，逐個比較每個元素的大小，直到找到相應的位置。

   這個算法中絲毫沒有考慮當要插入第 i 個元素時前面的 0~~ i -1 序列是有序的這個特點。今天要總結的這個算法就充分的利用了這一點。

算法的基本過程：

   1）計算 0 ~ i-1 的中間點，用 i 索引處的元素與中間值進行比較，如果 i 索引處的元素大，說明要插入的這個元素應該在中間值和剛加入i索引之間，反之，就是在剛開始的位置 到中間值的位置，這樣很簡單的完成了折半；

   2）在相應的半個範圍裡面找插入的位置時，不斷的用（1）步驟縮小範圍，不停的折半，範圍依次縮小為 1/2  1/4  1/8 .......快速的确定出第 i  個元素要插在什麼地方；

   3）确定位置之後，将整個序列後移，并将元素插入到相應位置。

算法實作：

 輸出截圖：

算法分析：

   1）時間複雜度：

   折半插入排序比直接插入排序明顯減少了關鍵字之間的比較次數，但是移動次數是沒有改變。是以，折半插入排序和插入排序的時間複雜度相同都是o（n^2），在減少了比較次數方面它确實相當優秀，是以該算法仍然比直接插入排序好。

   2）空間複雜度：

   折半插入排序和插入排序一樣隻需要一個多餘的緩存資料單元來放第 i 個元素，是以空間複雜度是o（1），因為排序前2個相等的數在序列的前後位置順序和排序後它們兩個的前後位置順序相同，是以它是一個穩定排序。 

如果，您認為閱讀這篇部落格讓您有些收獲，不妨點選一下右下角的【推薦】 

如果，您希望更容易地發現我的新部落格，不妨點選一下左下角的【關注我】 

如果，您對我的部落格内容感興趣，請繼續關注我的後續部落格，我是【orson】 

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段 聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。 

轉載：http://www.cnblogs.com/java-class/archive/2013/06/01/3112461.html