【排序算法】折半插入排序

1.折半插入排序的定义

　　折半插入算法是对直接插入排序算法的改进，它通过“折半查找”在比较区查找插入点的位置，这样可以减少比较的次数，但移动的次数不变。

2.折半插入排序的流程

• 把n个待排序的元素看成一个有序表和一个无序表，开始时有序表中只有一个元素，无序表中有n-1个元素；排序过程即每次从无序表中取出第一个元素，将它插入到有序表中，

• 插入过程：对于折半插入排序而言，当需要插入第i个元素时，它不会逐个进行比较每个元素，而是：

  • 计算0~n-1索引的中间点，也就是用i索引处的元素和(0+n-1)/2索引处的元素进行比较，如果i索引处的元素值大，就直接在(0+n-1)/2~n-1半个范围内进行搜索；反之在0~(0+n-1)/2半个范围内搜索，这就是所谓的折半；
  • 在半个范围内搜索时，按照上面的方法不断地进行折半搜索，这样就可以将搜索范围缩小到1/2、1/4、1/8…，从而快速的确定插入位置；

• 最后使之成为新的有序表，重复n-1次完成整个排序过程。

3.折半插入排序的代码实现

public class BinaryInsertSort {
    public static void main(String[] args) {
        int data[] = {3,1,5,7,2,4,9,6};
        binaryInsertSort(data);
        System.out.print("折半插入排序后：");
        printResult(data);
    }

    private static void binaryInsertSort(int[] a) {
        int n = a.length;
        int i,j;
        for(i=1;i<n;i++){
            //temp为本次循环待插入有序列表中的数
            int temp = a[i];
            int low=0;
            int high=i-1;
            //寻找temp插入有序列表的正确位置，使用二分查找法
            while(low <= high){
                //有序数组的中间坐标，此时用于二分查找，减少查找次数
                int mid = (low+high)/2;
                //若有序数组的中间元素大于待排序元素，则有序序列向中间元素之前搜索，否则向后搜索
                if(a[mid]>temp){
                    high = mid-1;
                }else{
                    low = mid+1;
                }
            }

            for(j=i-1;j>=low;j--){
                //元素后移，为插入temp做准备
                a[j+1] = a[j];
            }

            //插入temp
            a[low] = temp;
        }
    }

    //打印排序的最终结果
    private static void printResult(int[] a){
        for(int j=0;j<a.length;j++){
            System.out.print(" "+a[j]);
        }
        System.out.println();
    }
}

4.算法分析

折半查找只是减少了比较次数，但是元素的移动次数不变。因此，它的 空间复杂度 O(1) ，时间复杂度O(n^2)，是一种稳定的排序算法。

本人才疏学浅，若有错，请指出
谢谢！

最后

以上就是干净冰淇淋为你收集整理的【排序算法】折半插入排序的全部内容，希望文章能够帮你解决【排序算法】折半插入排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。