插入排序

插入排序也是一类非常常见的排序方法，它主要包含直接插入、折半插入和Shell排序等几种常见排序方法。

直接插入排序

直接插入排序的思路非常简单：依次将待排序的数据元素按其关键字值的大小插入前面的有序序列。
细化来说，对于一个有n个元素数据序列，排序需要进行n-1趟插入操作，如下所示。
第1趟插入：将第2个元素插入前面的有序子序列—此时前面只有一个元素，当然是有序的。
第2趟插入：将第3个元素插入前面的有序子序列，前面2个元素是有序的。
……
第n-1趟插入：将第n个元素插入前面的有序子序列，前面n-1个元素是有序的。

public class InsertSort {
    public static void insertSort(DataWrap[] data) {
        System.out.println("开始排序：" + Arrays.toString(data));

        int arrayLength = data.length;

        for (int i = 1; i < arrayLength; i++) {
            //当整体后移时，保证data[i]的值不会丢失
            DataWrap tmp = data[i];
            //i索引处的值已经比前面所有值都大，表明已经有序，无需插入
            //因为i-1索引之前的数据已经是有序的，i-1索引处的值就是最大值
            if (data[i].compareTo(data[i - 1]) < 0) {
                int j = i - 1;
                //整体后移一格，并且只有data[j]的值比tmp大才往后移
                for (; j >= 0 && data[j].compareTo(tmp) > 0; j--) {
                    data[j + 1] = data[j];
                }
                //最后将tmp的值插入合适位置
                data[j + 1] = tmp;
            }
            System.out.println(Arrays.toString(data));
        }
    }

    public static void main(String[] args) {
        DataWrap[] data = new DataWrap[]{
                new DataWrap(9, ""),
                new DataWrap(-16, ""),
                new DataWrap(21, "*"),
                new DataWrap(23, ""),
                new DataWrap(-30, ""),
                new DataWrap(-49, ""),
                new DataWrap(21, ""),
                new DataWrap(30, ""),
                new DataWrap(13, "")
        };

        System.out.println("排序前：" + Arrays.toString(data));
        insertSort(data);
        System.out.println("排序后：" + Arrays.toString(data));
    }
}

总结

直接插入的时间效率并不高，如果在最坏情况下，所有元素的比较次数总和为（0+1+...+n-1)=O(n²)，故时间复杂度为O(n²)
只需要一个缓存单元，所以空间效率为O(1)
直接插入排序是稳定的

折半插入排序

折半插入排序是对直接插入排序的简单改进。对于简单插入排序而言，当第i-1 趟需要将第i个元素插入前面的0～i-1个元素序列中时，它总是从i-1个元素开始，逐个比较每个元素，直到找到它的位置。这显然没有利用前面0～i-1个元素已经有序这个特点，而折半插入排序则改进了这一点。
对于折半插入排序而言，当第i-1趟需要将第i个元素插入前面的0～i-1个元素序列中时，它不会直接从i-1个元素开始逐个比较每个元素。折半插入排序的做法如下。
(1) 计算 0～i-1 索引的中间点，也就是用i 索引处的元素和(0+i-1)/2 索引处的元素进行比较，如果i索引处的元素大，就直接在(0+i-1)/2～i-1半个范围内搜索；反之，就在0～(0+i-1)/2半个范围内搜索，这就是所谓的折半。
(2) 在半个范围内搜索时，再按（1）步方法进行折半搜索。总是不断地折半，这样就可以将搜索范围缩小到1/2、1/4、1/8，从而快速确定第i个元素的插入位置
(3) 一旦确定了第i个元素的插入位置，剩下的事情就简单了。程序将该位置以后的元素整体后移一位，然后将第i个元素放入该位置

public class BinaryInsertSort {
    public static void binaryInsertSort(DataWrap[] data){
        System.out.println("开始排序：");
        int arrayLength = data.length;
        for (int i = 1; i < arrayLength; i++) {
            //当整体后移时，保证data[i]的值不会丢失
            DataWrap tmp = data[i];
            int low = 0;
            int height = i-1;

            while (low <= height) {
                //找出low,height中间的索引
                int middle = (low+height)/2;

                //如果tmp大于low，height中间的值
                if (tmp.compareTo(data[middle]) > 0) {
                    //限制在索引大于middle的那一半中搜索
                    low = middle+1;
                }else{
                    height = middle-1;
                }
            }
            //将low处到i的所有元素向后整体移动一位
            for (int j = i; j > low; j--) {
                data[j] = data[j-1];
            }
            data[low] = tmp;
            System.out.println(Arrays.toString(data));

        }
    }

    public static void main(String[] args) {
        DataWrap[] data = new DataWrap[]{
                new DataWrap(9, ""),
                new DataWrap(-16, ""),
                new DataWrap(21, "*"),
                new DataWrap(23, ""),
                new DataWrap(-30, ""),
                new DataWrap(-49, ""),
                new DataWrap(21, ""),
                new DataWrap(30, ""),
                new DataWrap(13, "")
        };

        System.out.println("排序前：" + Arrays.toString(data));
        binaryInsertSort(data);
        System.out.println("排序后：" + Arrays.toString(data));
    }
}

总结

折半插入排序的效果与直接插入排序的效果基本相同，只是更快了一些，因为折半插入排序可以更快地确定第i个元素的插入位置。

Shell排序

Shell排序对直接插入排序进行了简单改进：它通过加大插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项大跨度地移动。当这些数据项排过一趟序后，Shell排序算法减小数据项的间隔再进行排序，依此进行下去。进行这些排序时的数据项之间的间隔被称为增量，习惯上用字母h来表示这个增量。

public class ShellSort {

    public static void shellSort(DataWrap[] data) {
        System.out.println("排序开始：");
        int arrayLength = data.length;

        //h变量保存可变增量
        int h = 1;
        //按h*3+1得到增量序列的最大值
        while (h <= arrayLength / 3) {
            h = h * 3 + 1;
        }
        while (h > 0) {
            System.out.println("====h的值：" + h + " ====");
            for (int i = h; i < arrayLength; i++) {
                //当整体后移时，保证data[i]的值不会丢失
                DataWrap tmp = data[i];
                //i索引处的值已经比前面所有的值都大，表明已经有序，无需插入
                //(i-1索引之前的数据已经有序，i-1索引处元素的值就是最大值)
                if (data[i].compareTo(data[i - h]) < 0) {
                    int j = i - h;
                    //整体后移h格
                    for (; j >= 0 && data[j].compareTo(tmp) > 0; j -= h) {
                        data[j+h] = data[j];
                    }
                    data[j + h] = tmp;
                }
                System.out.println(Arrays.toString(data));
            }
            h = (h-1)/3;
        }
    }

    public static void main(String[] args) {
        DataWrap[] data = {
                new DataWrap(9, ""),
                new DataWrap(-16, ""),
                new DataWrap(21, "*"),
                new DataWrap(23, ""),
                new DataWrap(-30, ""),
                new DataWrap(-49, ""),
                new DataWrap(21, ""),
                new DataWrap(30, "*"),
                new DataWrap(30, "")
        };

        System.out.println("排序前：\n" + Arrays.toString(data));
        shellSort(data);
        System.out.println("排序后：\n" + Arrays.toString(data));

    }
}

总结

shell排序的空间开销在O(1)
shell排序是稳定的