1.2.2折半插入排序
原理：有一组数据待排序，排序区间为Array[0]~Array[n-1]。将数据分为有序数据和无序数据，第一次排序时默认Array[0]为有序数据，Array[1]~Array[n-1]为无序数据。有序数据分区的第一个元素位置为low，最后一个元素的位置为high。遍历无序区间的所有元素，每次取无序区间的第一个元素Array[i]，因为0~i-1是有序排列的，所以用中点m将其平分为两部分，然后将待排序数据同中间位置为m的数据进行比较，若待排序数据较大，则low~m-1分区的数据都比待排序数据小，反之，若待排序数据较小，则m+1~high分区的数据都比 待排序数据大，此时将low或high重新定义为新的合适分区的边界，对新的小分区重复上面操作。直到low和high 的前后顺序改变，此时high+1所处位置为待排序数据的合适位置。
实例：
以i=4时为例：
第一步
第二步
第三步：
第四步：
第五步：
第六步：
第七步：
性能分析：
空间效率：O(1)
时间效率：O(n^2)
稳定性：稳定
折半插入排序仅仅减少了比较元素的次数，约为（nlog2n）,该比较次数与待排序表的初始状态无关，仅仅取决于表中的元素个数n,而元素的移动次数没有改变，它依赖于待排序表的初始状态。
import java.util.Scanner; import java.util.Arrays; public class ZheBanInsertSort { private static void zheBanInsert(int[] arr) { for (int i=1;i<arr.length;i++){ int temp = arr[i]; // 用折半查找法去查找 int low = 0; int high = i-1; while (low<=high){ int mid = (low+high)/2; if (arr[mid]>temp){ high = mid - 1; }else { low = mid + 1; } } // 确定最后的位置为low或者high+1 for (int j=i-1;j>=low;j--){ arr[j+1] = arr[j]; } // 赋值 arr[low] = temp; } System.out.println("折半插入排序："+Arrays.toString(arr)); } public static void main(String[] args) { Scanner scanner = new Scanner(System.in);//Scanner工具类键盘输入数据 while (scanner.hasNext()) { int n = scanner.nextInt(); if (n > 0) { int arr[] = new int[n]; for (int i = 0; i < n; i++) { arr[i] = scanner.nextInt(); } zheBanInsert(arr);//调用折半插入排序zheBanInsert方法 } } } }
