排序之折半插入排序

简介

二分查找（折半插入）排序属于插入类排序的一种，可以说是直接插入排序的一种改进版：主要改进在查找插入位置上节省了时间。

直接插入排序需要依次在有序的序列里进行比较，较大值右移一直到找到合适的位置进行插入。

二分查找排序节省了查找的时间。对于一个有序的序列来说，采用二分查找的方式来找到插入点比直接便利比较所费的时间少。使用二分查找排序找到插入点之后，依次后移插入点之后的数据，然后将要插入的值放进去，完成一次插入操作。

二分查找排序思想

二分查找排序主要基于对查找插入位置的时间进行优化，使用二分查找来缩短插入位置的查找时间。对于待排序的一个序列来说，假设要插入的是第N个数，则说明前N-1个数已经为有序，那么我们需要将第N个数插入到前N-1个数的序列中。

那么我们根据第N个数的值可以使用二分查找来找到前N-1个数的插入点位置。之后将插入点之后的值依次后移一位。最后将第N个值插入。这样，我们完成了依次插入过程，之后依次将剩余数字按照如上方式进行插入，最后实现序列有序。

二分查找排序代码

private static void binaryInsertSort(int[] array) { if (array == null || array.length == 0) { return; } int length = array.length; int temp = 0; int pre = 0; int last = 0; for (int i = 1; i < length; i++) { //要插入的值 temp = array[i]; pre = 0; last = i - 1; while (pre <= last) { int middle = (pre + last) >> 1; if (temp > array[middle]) { pre = middle + 1; } else if (temp < array[middle]) { last = middle - 1; } } //找到插入位置之后，将插入点之后的数据后移一位 for (int j = i - 1; j >= pre; j--) { array[j + 1] = array[j]; } array[pre] = temp; } }

总结

折半插入排序其实就是直接插入排序的一种改进，引入了二分查找算法，这样关键字的比较次数就会减少，数量级为O(nlog^2n)，但是元素移动次数还是O(n^2)，所以折半插入排序的时间复杂度是O(n^2)。

另外，折半插入排序是稳定的排序算法；