算法（二）初等排序前篇[插入和希尔排序]

本文首发于微信公众号「后厂技术官」

前言

排序是算法的基础，排序有很多种方法，有些方法实现起来很简单，但是效率较差，我们可以将这些排序的方法称之为初等排序。这篇文章我们就来学习初等排序中的插入排序和希尔排序。

1.插入排序

插入排序比较容易想到，思路与打扑克时排列牌的顺序是类似的。比如我们左手拿牌，然后用右手将牌从左到右，从小到大来排序，这就需要我们把需要进行排列的牌抽出来放到合适的位置，并且不断的重复，直到牌的顺序排好，这个过程就可以理解为插入排序。

图解插入排序

插入排序过程中会将需要排序的数组，分为两个部分：已排序部分和未排序部分，如下图所示。

从图中可以看出这个数组分为两个部分，其中下标为0、1、2的元素为已排列部分，其余的则为未排列部分。

插入的排序规则：
将开头元素视为以排序部分。接着执行如下的处理，直到没有未排序部分。

取出未排序部分的开头元素赋值给临时保存数据的变量v。
在已排列的部分将所有比v大的元素向后移动一个位置。
将取出的元素v插入空位。

按照这个规则，我们来举一个简单的例子。我们对数组 a={8,3,1,5,2,1} 进行从小到大排序，数组a如下图所示。

我们对数组a进行排序，共需要5个步骤：
1.接着我们将a[0]=8视为已排序，我们从a[1]开始操作，将a[1]的值3取出，3要小于a[0]的值8，因此将a[0]的值8移动到a[1]，再把3插入到a[0]，如下图所示。

2.a[2]的值1要比a[0]和a[1]的值要小，则将a[0]和a[1]顺次向后移一个位置，然后将1插入a[0]，如下图所示。

3.将a[3]中的5拿出来，比它大的是a[2]的8，因此8向后移，将5插入a[3]。如下图所示。

4.将a[4]中2拿出来，发现a[1]、a[2]、a[3]中的值都比2大，因此将它们依次向后移，将2插入到a[1]中，如下图所示。

5.最后将a[5]中的1移到合适的位置，过程和上面一样，最后的排序结果如下图所示。

实现插入排序

接下来要实现插入排序，针对下图来定义变量。

如上图所示，i代表未排序部分的开头元素，v是临时保存a[i]值的变量， j代表已排序部分v要插入的位置。
根据定义的这三个变量，插入排序的实现思路就是：外层循环i从1开始自增，并在每次循环开始时将a[i]的值保存在v中；内层循环则是j从i-1开始向前自减，并将比v大的元素从a[j]移动到a[j+1]，并将v插入到当前j+1的位置（内层循环后，j会先自减1，因此插入的地方则是j+1的位置），当j等于-1或者a[j]小于等于v则内层循环结束。
接下来我们用代码来实现插入排序，如下所示。

public class InsertSort {
    public static void main(String[] args) {
        int a[] = {8, 3, 1, 5, 2, 1};
        ArrayUtils.printArray(a);
        int b[] = insert(a);
        ArrayUtils.printArray(b);
    }
    public static int[] insert(int[] a) {
        int i, j, v;
        int n = a.length;
        for (i = 1; i < n; i++) {
            v = a[i];
            j = i - 1;
            while (j >= 0 && a[j] > v) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = v;
        }
        return a;
    }
}

其中负责打印数组的ArrayUtils类如下所示。

public class ArrayUtils {
    public static void printArray(int[] array) {
        System.out.print("{");
        int len=array.length;
        for (int i = 0; i < len; i++) {
            System.out.print(array[i]);
            if (i < len - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("}");
    }
}

输出结果为：
{8, 3, 1, 5, 2, 1}
{1, 1, 2, 3, 5, 8}

插入排序的复杂度

根据算法（一）时间复杂度所讲的，我们来算一下插入排序的时间复杂度。在最坏的情况下，每个i循环都需要执行i次移动，总共需要1+2+……+n-1=n²/2+n/2，根据此前讲过的推导大O阶的规则的我们得出插入排序的时间复杂度为O(n²)。

2.希尔排序

插入排序对于大规模的乱序数组，插入排序会很慢，因为它只会交换相邻的元素，元素只能一点一点的从数组的一端移动到另一端。如果最小的元素在数组的末尾，则要将它移动到数组的开头则需要进行n-1次移动。

希尔排序原理

希尔排序改进了插入排序这一问题，它交换不相邻的元素对数组进行局部排序，并最终用插入排序将局部有序的数组进行排序。
希尔排序的思想就是使得数组中任意间隔h的元素都是有序的，这样的数组可以成为h有序数组。这里拿数组a={4,8,9,1,10,6,2,5}为例，当h为4时，会将这个数组分为h个子数组。

从上图可以看到，我们根据h=4，将数组分为了四个子数组，分别是{4,10}、{8,2}、{1,5}、{10,3}。我们分别对这四个子数组进行局部排序，接下来对h进行递减操作，直到h为1，这样最后一次循环就是一个典型的插入排序。

实现希尔排序

我们将数组分为h个数组，我们将子数组的每个元素交换到比他大的元素前面去，只需要将插入排序的将移动元素的距离1改为h即可。这样希尔排序的实现就转换为了一个类似于插入排序但使用的增量不同的过程。
代码实现如下所示。

public class ShellSort {
    public static void main(String[] args) {
        int a[] = {4, 8, 9, 1, 10, 6, 2, 5};
        ArrayUtils.printArray(a);
        int b[] = shellSort(a);
        ArrayUtils.printArray(b);
    }
    public static int[] shellSort(int[] a) {
        int h = 1;
        int n = a.length;
        while (h < n / 3) //1
            h = 3 * h + 1;
        while (h >= 1) {
        //增量为h的插入排序
            for (int i = h; i < n; i++) {
                int v = a[i];
                int j = i - h;
                while (j >= 0 && a[j] > v) {
                    a[j + h] = a[j];
                    j -= h;
                }
                a[j + h] = v;
            }
            h = h / 3;
        }
        return a;
    }
}

注释1处的代码是为了得到h值，关于h选什么样的值是最好的，至今还未有定论，这里我们给出比较常用的h值为h = 3 * h + 1，也就是1、4、13、40、121、346、1093……，这些h值会根据数组的大小而改变。接着往下看，下面的代码则是一个增量为h的插入排序。
输出结果为：
{4, 8, 9, 1, 10, 6, 2, 5}
{1, 2, 4, 5, 6, 8, 9, 10}