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

摘要：今天再来看看另外三种时间复杂度都是的排序算法，分别是希尔排序归并排序和快速排序。三数取中法求将放到数组的末尾总结这三种排序算法的平均时间复杂度都是，归并排序和快速排序的应用更广泛。

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) 。