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

1. 回顾

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

2. 希尔排序

先来看看希尔排序,它是较早突破 O(n2) 的时间复杂度的算法之一,其实是对插入排序的一种优化。前面说到的插入排序,操作非常的机械,就是按照固定顺序逐步比较大小,但是遇到一些比较极端的情况,数据移动的操作就会很频繁,比如排序数组 [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(n2) 了。我们的理想是,大于分区点和小于分区点的数据是均匀分布的,不会出现太多或太少的情况。

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

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)

相关推荐