折半插入排序稳定吗_数据结构之插入排序（折半插入排序）

排序思路：通过折半查找的方式找到合适的插入位置再插入。

算法实现：

public class BiInsertSort {    public static void biInsertSort(int arr[]){        for(int i = 1; i < arr.length; i ++){            int temp = arr[i];            int left = 0;            int right = i-1;            while(left <= right){//通过拆装查找找到插入位置                int mid = (left+right)/2;                if(temp < arr[mid]){//插入点在[left,mid-1]                    right = mid-1;                }else               //插入点在[mid+1,right]                    left = mid+1;            }//直到找到合适的位置(left或right+1)，接下来就将left/right+1后的元素后移            for(int j = i-1;j >= right+1; j --){                arr[j+1] = arr[j];            }            arr[right+1] = temp;        }            }    public static void main(String[] args) {        int array[] = {2,5,3,1,5,2,8};        System.out.println("排序之前：");        for(int element : array){            System.out.print(element+" ");        }                biInsertSort(array);        System.out.println("排序之后：");        for(int element : array){            System.out.print(element+" ");        }    }}

算法分析：不管元素的初始序列为正序还是反序，其时间复杂度都和直接插入排序的一样为O(n2)。不同的是折半插入排序中查找的平均比较次数为log2(i+1)-1,

所以就平均性能而言，折半插入排序优于直接插入排序。同样，折半插排序的空间复杂度也是O(1),且也是一种稳定的排序。