1. 折半插入排序是對直接插入排序演算法的改進，在直接插入排序演算法中，不難看出每趟插入的程序中，都進行了兩項作業：（1）從前面的有序子表中查找出待插入元素應該被插入的位置；(2)給插入位置騰出空間，將待插入元素復制到表中的插入位置，注意到該演算法中，總是邊比較邊移動元素，下面將比較和移動操作分離出來，即先折半查找出元素的待插入位置，然后再統一地移動待插入位置之后的所有元素，當排序表為順序存盤的線性表時，可以對直接插入排序演算法作如下改進：在查找子表時可以折半查找待插入元素的位置，在確定出待插入位置后，就可以統一地向后移動元素了，
2. 折半插入代碼實作
1 package cn.sun.it.review; 2 3 import java.util.Arrays; 4 import java.util.Scanner; 5 6 public class BinaryInsertSort { 7 8 public static void main(String[] args) { 9 // 測驗資料：5,3,6,2,1,9,4,8,7 10 System.out.println("請輸入若干個整數，以逗號分隔："); 11 Scanner sc = new Scanner(System.in); 12 String strNums = sc.nextLine(); 13 String[] tempArrNums = strNums.split(","); 14 int[] arr = new int[tempArrNums.length]; 15 for (int i = 0; i < arr.length; i++) { 16 arr[i] = Integer.valueOf(tempArrNums[i]); 17 } 18 System.out.println("排序前：" + Arrays.toString(arr)); 19 binaryInsertSort(arr); 20 System.out.println("排序后：" + Arrays.toString(arr)); 21 } 22 23 private static void binaryInsertSort(int[] arr) { 24 int temp; 25 for (int i = 1; i < arr.length; i++) { 26 if (arr[i] < arr[i - 1]) { 27 // 快取i處元素的值 28 temp = arr[i]; 29 // 記錄搜索范圍的左邊界 30 int low = 0; 31 // 記錄搜索范圍的右邊界 32 int high = i - 1; 33 while (low <= high) { 34 // 記錄中間位置 35 int mid = (low + high) / 2; 36 // 比較有序子表中間位置資料和i處資料的大小，以縮小搜索范圍 37 if(arr[mid] < temp){ 38 low = mid+1; 39 }else{ 40 high = mid-1; 41 } 42 } 43 // 將low ~ i處的資料整體向后移動1位 44 for(int j=i;j>low;j--){ 45 arr[j] = arr[j-1]; 46 } 47 arr[low] = temp; 48 } 49 } 50 } 51 52 }
3. 折半插入排序性能
（3.1） 折半插入排序僅僅是減少了比較元素的次數，約為O(nlog2n)，該比較次數與待排序表的初始狀態無關，僅取決于表中的元素個數n;
（3.2）而元素的移動次數沒有改變，它依賴于待排序表的初始狀態，其時間復雜度仍為O(n2)
（3.3）折半插入排序是一個穩定的排序演算法
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/270654.html
標籤：其他