排序（sort）- 下

归并排序（Merge Sort）

归并排序算法原理

先把数组从中间分成前后两部分，然后对前后两部分分别进行排序，再将排序好的两部分合并到一起，这样整个数组就有序了。这就是归并排序的核心思想。如何用递归实现归并排序呢？写递归代码的技巧就是分写得出递推公式，然后找到终止条件，最后将递推公式翻译成递归代码。递推公式怎么写？如下

1 2	递推公式：merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r)) 终止条件：p >= r 不用再继续分解

归并排序代码实现

public class MergeSort {

    // 归并排序算法，a 是数组，n 表示数组大小
    public static void mergeSort(int[] a, int n) {
        mergeSortInternally(a, 0, n - 1);
    }

    // 递归调用函数
    private static void mergeSortInternally(int[] a, int p, int r) {
        // 递归终止条件
        if (p >= r) return;

        // 取 p 到 r 之间的中间位置 q, 防止（p+r）的和超过 int 类型最大值
        int q = p + (r - p) / 2;
        // 分治递归
        mergeSortInternally(a, p, q);
        mergeSortInternally(a, q + 1, r);

        // 将 A[p...q] 和 A[q+1...r] 合并为 A[p...r]
        merge(a, p, q, r);
    }

    private static void merge(int[] a, int p, int q, int r) {
        int i = p;
        int j = q + 1;
        int k = 0; // 初始化变量 i, j, k
        int[] tmp = new int[r - p + 1]; // 申请一个大小跟 a[p...r] 一样的临时数组
        while (i <= q && j <= r) {
            if (a[i] <= a[j]) {
                tmp[k++] = a[i++]; // i++等于 i:=i+1
            } else {
                tmp[k++] = a[j++];
            }
        }

        // 判断哪个子数组中有剩余的数据
        int start = i;
        int end = q;
        if (j <= r) {
            start = j;
            end = r;
        }

        // 将剩余的数据拷贝到临时数组 tmp
        while (start <= end) {
            tmp[k++] = a[start++];
        }

        // 将 tmp 中的数组拷贝回 a[p...r]
        for (i = 0; i <= r - p; ++i) {
            a[p + i] = tmp[i];
        }
    }

}

归并排序性能分析

归并排序算法稳定性：

归并排序稳不稳定关键要看 merge() 函数，也就是两个子数组合并成一个有序数组的那部分代码。在合并的过程中，如果 A[p…q] 和 A[q+1…r] 之间有值相同的元素，那我们就可以像伪代码中那样，先把 A[p…q] 中的元素放入 tmp 数组，这样就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一种稳定排序算法。

归并排序时间复杂度：

分析归并排序的时间复杂度就是分析递归代码的时间复杂度，如何分析递归代码的时间复杂度？

递归的适用场景是一个问题 a 可以分解为多个子问题 b、c，那求解问题 a 就可以分解为求解问题 b、c。问题 b、c 解决之后，我们再把 b、c 的结果合并成 a 的结果。若定义求解问题 a 的时间是 T(a)，则求解问题 b、c 的时间分别是 T(b) 和 T(c)，那就可以得到这样的递推公式：T(a) = T(b) + T(c) + K，其中 K 等于将两个子问题 b、c 的结果合并成问题 a 的结果所消耗的时间。这里有一个重要的结论：不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式。套用这个公式，那么归并排序的时间复杂度就可以表示为：

T(1) = C； n=1 时，只需要常量级的执行时间，所以表示为 C。
T(n) = 2*T(n/2) + n； n>1，其中 n 就是 merge() 函数合并两个子数组的的时间复杂度 O(n)。
T(n) = 2*T(n/2) + n
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
     ......
     = 2^k * T(n/2^k) + k * n
     ......

当 T($n/2^k$)=T(1) 时，也就是 $n/2^k=1$，我们得到$k=\log_2 n$。将 k 带入上面的公式就得到$T(n)=Cn+n\log_2 n$。如用大 O 表示法，T(n) 就等于 O($n\log n$)。所以，归并排序的是复杂度时间复杂度就是 O($n\log n$)。

归并排序空间复杂度：

归并排序算法不是原地排序算法，空间复杂度是 O(n)

为什么？因为归并排序的合并函数，在合并两个数组为一个有序数组时，需要借助额外的存储空间。为什么空间复杂度是 O(n) 而不是 O($n\log n$) 呢？如果我们按照分析递归的时间复杂度的方法，通过递推公式来求解，那整个归并过程需要的空间复杂度就是 O($n\log n$)，但这种分析思路是有问题的！因为，在实际上，递归代码的空间复杂度并不是像时间复杂度那样累加，而是这样的过程，即在每次合并过程中都需要申请额外的内存空间，但是合并完成后，临时开辟的内存空间就被释放掉了，在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时空间再大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。

快速排序（Quick Sort）

快速排序算法原理

快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。然后遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 povit 放到中间。经过这一步之后，数组 p 到 r 之间的数据就分成了 3 部分，前面 p 到 q-1 之间都是小于 povit 的，中间是 povit，后面的 q+1 到 r 之间是大于 povit 的。根据分治、递归的处理思想，我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，直到区间缩小为 1，就说明所有的数据都有序了。

1 2	递推公式：quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r) 终止条件：p >= r

快速排序代码实现

public class QuickSort {

    // 快速排序，a 是数组，n 表示数组的大小
    public static void quickSort(int[] a, int n) {
        quickSortInternally(a, 0, n - 1);
    }

    // 快速排序递归函数，p,r 为下标
    private static void quickSortInternally(int[] a, int p, int r) {
        if (p >= r) return;

        int q = partition(a, p, r); // 获取分区点
        quickSortInternally(a, p, q - 1);
        quickSortInternally(a, q + 1, r);
    }

    private static int partition(int[] a, int p, int r) {
        int pivot = a[r];
        int i = p;
        for (int j = p; j < r; ++j) {
            if (a[j] < pivot) {
                if (i == j) {
                    ++i;
                } else {
                    int tmp = a[i];
                    a[i++] = a[j];
                    a[j] = tmp;
                }
            }
        }

        int tmp = a[i];
        a[i] = a[r];
        a[r] = tmp;

        System.out.println("i=" + i);
        return i;
    }

}

快速排序性能分析

快速排序算法稳定性：

因为分区过程中涉及交换操作，如果数组中有两个 8，其中一个是 pivot，经过分区处理后，后面的 8 就有可能放到了另一个 8 的前面，先后顺序就颠倒了，所以快速排序是不稳定的排序算法。比如数组 [1,2,3,9,8,11,8]，取后面的 8 作为 pivot，那么分区后就会将后面的 8 与 9 进行交换。

快速排序时间复杂度：最好、最坏、平均情况

快排也是用递归实现的，所以时间复杂度也可以用递推公式表示。

如果每次分区操作都能正好把数组分成大小接近相等的两个小区间，那快排的时间复杂度递推求解公式跟归并的相同。

1 2	T(1) = C； n=1 时，只需要常量级的执行时间，所以表示为 C。 T(n) = 2*T(n/2) + n； n>1

所以，快排的时间复杂度也是 O($n\log n$)。

如果数组中的元素原来已经有序了，比如 1，3，5，6，8，若每次选择最后一个元素作为 pivot，那每次分区得到的两个区间都是不均等的，需要进行大约 n 次的分区，才能完成整个快排过程，而每次分区我们平均要扫描大约 n/2 个元素，这种情况下，快排的时间复杂度就是 O($n^2$)。

前面两种情况，一个是分区及其均衡，一个是分区极不均衡，它们分别对应了快排的最好情况时间复杂度和最坏情况时间复杂度。那快排的平均时间复杂度是多少呢？T(n) 大部分情况下是 O($n\log n$)，只有在极端情况下才是退化到 O($n^2$)，而且我们也有很多方法将这个概率降低。

快速排序空间复杂度：

快排是一种原地排序算法，空间复杂度是 O(1)

归并排序与快速排序的区别

归并和快排用的都是分治思想，递推公式和递归代码也非常相似，那它们的区别在哪里呢？

归并排序，是先递归调用，再进行合并，合并的时候进行数据的交换。所以它是自下而上的排序方式。何为自下而上？就是先解决子问题，再解决父问题。
快速排序，是先分区，在递归调用，分区的时候进行数据的交换。所以它是自上而下的排序方式。何为自上而下？就是先解决父问题，再解决子问题。

江城子的博客

数据结构与算法之美（五）