数据结构与算法——希尔、归并、快速排序

1. 回顾

前面说完了三种较为简单的排序算法，分别是冒泡排序，选择排序和插入排序，它们的平均情况时间复杂度都是 O(n²)，比较的高，适合小规模的数据排序，其中插入排序的效率稍高，所以更推荐使用插入排序。今天再来看看另外三种时间复杂度都是 O(nlogn) 的排序算法，分别是希尔排序、归并排序和快速排序。其中后两者的应用非常的广泛。

2. 希尔排序

先来看看希尔排序，它是较早突破 O(n²) 的时间复杂度的算法之一，其实是对插入排序的一种优化。前面说到的插入排序，操作非常的机械，就是按照固定顺序逐步比较大小，但是遇到一些比较极端的情况，数据移动的操作就会很频繁，比如排序数组 [3, 5, 1, 7, 9, 0] ，要将最后的 0 移动到最前面，几乎会遍历整个数组。

所以，希尔排序对此进行了优化，采用一种分组策略，来缩小数据的移动，使数组整体是基本有序的，小的在前，大的在后，然后缩小增量，这样数据的移动就会比较的少。

结合图来理解一下：

先将数组分为 4 组，分别进行插入排序，然后再分为 2 组，再进行插入排序。最后分为一组，即数组本身，因为此时数据已经基本上是有序的了，所以只需要进行微调即可。

下面是它的代码实现：

public class ShellSort {

    public static void shellSort(int[] data) {
        int length = data.length;
        if (length <= 1) return;

        //确定增量
        int gap = length / 2;
        while (gap >= 1){
            for (int i = gap; i < length; i++) {
                int value = data[i];
                int j = i - gap;
                for (; j >= 0; j -= gap){
                    if (data[j] > value) data[j + gap] = data[j];
                    else break;
                }
                data[j + gap] = value;
            }
            //更新增量
            gap = gap / 2;
        }
    }
}

希尔排序并没有很广泛的应用，原因是比起归并排序，它是不稳定的，比起快速排序，它的执行效率稍低。

3. 归并排序

归并排序大致分为两个步骤，一是拆分，二是合并。将数组拆分为许多小的数组，将小的数组排序了，然后合并为大数组。这种思想叫做分治，即将一个大的问题分解成小的问题来解决。用到分治思想的问题大多可以使用递归这种编程技巧。

下面是它的图展示：

结合图分析，假如我们要排序 data[p - r] 这个数组，可以先排序 data[p - q] 和 data[q+1 - r]，然后进行合并。用公式可以这样表示：
merge_sort(data[p - r]) = merge(merge_sort(data[p - q]), merge_sort(data[q+1 - r]));

其中 merge 函数的作用是将两个已排序的数组进行合并，那么 merge 函数该如何表示呢？

思路其实很简单，新建一个临时数组，分别从头开始扫描两个子数组，比较大小，将小的放入到临时数组中，然后指针向后移，继续比较。你可以结合归并排序的代码实现来理解：

public class MergeSort {

    public static void mergeSort(int[] data) {
        mergeInternally(data, 0, data.length - 1);
    }

    private static void mergeInternally(int[] data, int p, int r){
        if (p >= r) return;

        //计算p到r的中间值
        int q = p + ((r - p) >> 1);
        //递归分解
        mergeInternally(data, p, q);
        mergeInternally(data, q + 1, r);
        //合并已排序数组
        merge(data, p, q, r);
    }

    private static void merge(int[] data, int p, int q, int r){
        int i = p;
        int j = q + 1;
        int k = 0;
        //初始化一个临时数组
        int[] temp = new int[r - p + 1];
        while (i <= q && j <= r){
            if (data[i] <= data[j]) temp[k ++] = data[i ++];
            else temp[k ++] = data[j ++];
        }
        //判断哪个数组中有剩余的数据
        int start = i;
        int end = q;
        if (j <= r){
            start = j;
            end = r;
        }
        //将剩余的数据拷贝到temp中
        while (start <= end){
            temp[k ++] = data[start ++];
        }
        //将temp拷贝到data中
        for (int t = 0; t <= r - p; t ++) {
            data[p + t] = temp[t];
        }
    }
}

4. 快速排序

快速排序的思路和上面的归并排序很类似，都用到了分治的思想，在数组中选取一个分区点，将大于分区点的数放在右边，小于分区点放在左边。然后依次递归完成排序。

在归并排序中有一个 merge 合并函数，在快速排序中有一个 partition 分区函数，这个函数的主要功能是选取分区点，然后将大于分区点的数据放在右边，小的放在左边，返回分区点下标。实现这个函数的思路比较的巧妙：

对于数组 data[p - r]，我们选取最后一个数据 data[r] 作为分区点，用两个指针 i，j 都指向数组第一个元素，如果 data[j] < data[r]，交换 data[i] 和 data[j] 的位置，i 和 j 都向前移动。如果 data[j] > data[r]，则不交换，i 不动，j 向前移动，直至到达数组末尾。

对于分区点的选择，其实直接选择数组的最后一个元素是有问题的，在极端的情况下，数组本来就是有序的，那么每次分区都会遍历整个数组，时间复杂度就退化为 O(n²) 了。我们的理想是，大于分区点和小于分区点的数据是均匀分布的，不会出现太多或太少的情况。

这里提供了另外两种解决办法：一是三数取中法，就是取数组中的头、中、尾三个数，比较大小，取中间大小的数作为分区点。二是随机法，即随机选取一个数作为分区点。我下面的代码实现便是使用的三叔取中法。

public class QuickSort {
    public static void quickSort(int[] data){
        quickSortInternally(data, 0, data.length - 1);
    }

    private static void quickSortInternally(int[] data, int p, int r){
        if (p >= r) return;
        int q = partition(data, p, r);

        quickSortInternally(data, p, q - 1);
        quickSortInternally(data, q + 1, r);
    }

    private static int partition(int[] data, int p, int r) {
        //三数取中法求pivot
        int q = p + ((r - p) >> 1);
        int mid = 0;
        if ((data[p] - data[q]) * (data[q] - data[r]) >= 0) mid = q;
        else if ((data[q] - data[p]) * (data[p] - data[r]) >= 0) mid = p;
        else mid = r;

        int pivot = data[mid];
        //将pivot放到数组的末尾
        swap(data, mid, r);

        int i = p;
        for (int j = p; j < r; j ++){
            if (data[j] < pivot){
                swap(data, i, j);
                i ++;
            }
        }
        swap(data, i, r);
        return i;
    }

    private static void swap(int[] data, int i, int j){
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

5. 总结

这三种排序算法的平均时间复杂度都是 O(nlogn) ，归并排序和快速排序的应用更广泛。

希尔排序和快速排序是不稳定的，没有借助额外的存储空间，因此空间复杂度是 O(1) 。

归并排序是稳定的，使用了临时数组，大小和排序数组大小相同，因此空间复杂度是 O(n) 。