折半插入排序

代码

package com.sort;

public class BInsertSort {

    public static void main(String[] args) {
        int[] arg = {5, 61, 7, 1, 2, 4, 3, 9, 4, 6, 54, 21};
        System.out.println("------------------------------");
        System.out.println("折半插入排序前：");
        PrintArg(arg);
        System.out.println("------------------------------");
        BinaryInsertSort(arg);
        System.out.println("------------------------------");
        System.out.println("折半插入排序后：");
        PrintArg(arg);
        System.out.println("------------------------------");
    }

    public static void BinaryInsertSort(int[] arg) {
        int length = arg.length;
        for (int i = 1; i < length; i++) {
            int low = 0;
            int high = i - 1;
            int temp=arg[i];
            while (low <= high) {
                int mid = (low + high) / 2;
                if (arg[i] < arg[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            for (int j = i; j >= low + 1; j--) {
                arg[j]=arg[j-1];
            }
            arg[low]=temp;
            System.out.println("第"+i+"趟排序后：");
            PrintArg(arg);
        }
    }

    //交换前后顺序
    public static void swap(int[] arg, int max, int min) {
        int temp;
        temp = arg[max];
        arg[max] = arg[min];
        arg[min] = temp;
    }

    //x>y——true;x<y——false
    public static boolean bigger(int x, int y) {
        if (x > y) {
            return true;
        } else {
            return false;
        }
    }

    //打印数组
    public static void PrintArg(int[] arg) {
        for (int i = 0; i < arg.length; i++) {
            if (i == arg.length - 1) {
                System.out.println(arg[i]);
            } else {
                System.out.print(arg[i] + " ");
            }

        }
    }

}

运行结果

原理

插入排序的基本思想是：每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。
直接插入排序采用顺序查找法查找当前记录在已排好序的序列中的插入位置，如果我们将这个“查找”操作利用“折半查找(二分查找)”来实现，由此进行的插入排序称之为“折半插入排序”。

算法分析

时间复杂度

从时间上比较，折半查找比顺序查找快，所以就平均性能来说，折半插入排序优于直接插入排序。
折半插入排序所需要的关键字比较次数与待排序序列的初始序列无关，仅依赖于记录的个数。无论初始序列情况如何，在插入第i个记录时，需要经过[log₂i]+1次比较，才能确定它应插入的位置。所以当记录的初始排列为正序或接近正序s，直接插入排序比折半插入排序执行的关键字比较次数要少。
折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列。
在平均情况下，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。因此，折半插入排序的时间复杂度仍为O(n²)。

空间复杂度

折半插入排序所需附加存储空间和直接插入排序相同，只需要一个记录的辅助空间，所以空间复杂度仍未O(1)。

算法特点

1. 稳定排序。
2. 因为要进行折半查找，所以只能用于顺序结构，不能用于链式结构。
3. 适合初始记录无序、n较大时的情况。

2018.10.17