归并排序与快排序

SilverLining

4年前

归并排序

传统的数组排序算法时间复杂度是 O(N^2)，因为每一次扫描数组，只能将 1 个数字移动到目标位置。每一个数的排序过程之间是互不关联的，也就浪费了一些有用的信息。

递归实现

我们用递归的思想来考虑排序问题，如果一个数组分为左右两部分，且两部分别都是有序的，那么我们只需要做一次 O(N)的操作，就可以将整个数组排序。这个操作就是归并排序核心的算法。

然后，为了合并整个大数组，我们先要将这个数组一分为二个部分，然后再继续分为两部分，直到达到最小子问题：当数组中只有一个元素时，他天然就是有序的。

public class MergeSort {

    public void recursiveMergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    private void process(int[] arr, int left, int right) {
        // base case
        if (left == right) {
            return;
        }
        int mid = left + ((right - left) >> 1);
        process(arr, left, mid);
        process(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    private void merge(int[] arr, int left, int mid, int right) {
        int[] help = new int[right - left + 1];
        int i = 0;
        int p1 = left;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= right) {
            if (arr[p1] <= arr[p2]) {
                help[i] = arr[p1];
                p1++;
            } else {
                help[i] = arr[p2];
                p2++;
            }
            i++;
        }
        // 要么 p1 越界，要么 p2 越界
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= right) {
            help[i++] = arr[p2++];
        }
        // 刷回结果
        for (i = 0; i < help.length; i++) {
            arr[left + i] = help[i];
        }
    }
}

迭代实现

因为递归实际上是使用了系统栈来实现的，因此理论上任何递归实现都可以改写为迭代实现。

归并排序的迭代实现，是反过来从 base case 考虑，先用 mergeSize = 1 将这个数组分成 N 组，两两之间排序；然后 mergeSize = 2，即已经排好序的每两个数组成一个新的组，将这 N/2 组两两排序；接着 mergeSize = 4，再做一次排序。

因为上一轮中已经保证了每个组上是有序的，因此可以在更大的范围上直接做归并。这就是迭代实现的思路。

public class MergeSort {

    public void iterativeMergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        // 左组 size
        int mergeSize = 1;
        // mergeSize = 1: [ 0 | 1 ] [ 2 | 3 ] [4 | 5 ] [ 6 | 7 ]
        // mergeSize = 2: [ 0...1 | 2...3 ] [ 4...5 | 6...7 ]
        // mergeSize = 4: [ 0...3 | 4...7 ]
        // mergeSize = 8: done

        while (mergeSize < N) {
            // 总是从 0 开始
            int left = 0;
            while (left < N) {
                int mid = left + mergeSize - 1;
                if (mid >= N) {
                    break;
                }
                int right = Math.min(mid + mergeSize, N - 1);
                merge(arr, left, mid, right);

                // move on next iteration
                left = right + 1;
            }

            // 此时左组长度已经超过了整个数组的一半，不需要再做下一轮归并了
            // 为了防止这时 mergeSize 很大（如已经逼近 N）
            // 乘 2 后远大于 N，在下一轮判断前就溢出，所以直接 break
            if (mergeSize > N / 2) {
                break;
            }
            mergeSize = mergeSize << 1;
        }
    }

    private void merge(int[] arr, int left, int mid, int right) {
        int[] help = new int[right - left + 1];
        int i = 0;
        int p1 = left;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= right) {
            if (arr[p1] <= arr[p2]) {
                help[i] = arr[p1];
                p1++;
            } else {
                help[i] = arr[p2];
                p2++;
            }
            i++;
        }
        // 要么 p1 越界，要么 p2 越界
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= right) {
            help[i++] = arr[p2++];
        }
        // 刷回结果
        for (i = 0; i < help.length; i++) {
            arr[left + i] = help[i];
        }
    }
}

时间复杂度

从迭代的实现上，可以看出，每一轮归并操作，时间复杂度为 O(N)，而 mergeSize 是 2 倍递增的，总共需要做 O(log N)轮归并，因此时间复杂度为

O(N \cdot \log_{}{N})

对于递归实现，有

T(N) = 2 \cdot T(\frac {N}{2}) + O(N^1) \\

\begin{aligned} \because a = 2, b = 2, d = 1 \\ \log_{b}{a} = 1, \log_{b}{a} = d \\ \therefore T(N) = O(N \cdot \log_{}{N}) \end{aligned}

为什么归并排序可以节省时间复杂度呢？

其本质是把比较行为变成了有序信息，并在每一次比较时向更大的组传递。

求数组的小和

在一个数组中，一个数左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫数组小和。比如：[1, 3, 4, 2, 5] 1 左边比 1 小的数：没有 3 左边比 3 小的数：1 4 左边比 4 小的数：1, 3 2 左边比 2 小的数：1 5 左边比 5 小的数：1, 3, 4, 2 所以数组的小和为 1+1+3+1+1+3+4+2=16

容易想到的暴力解法，是扫描两次数组，找到每个元素右边有几个数比他大。

我们想到在归并排序的归并操作中，就有比较两个数大小的逻辑。如果左组的数小于等于右组，就先拷贝左组的数，否则拷贝右组的数。那么，在归并操作调整顺序的过程中，我们就可以记下小和的信息。

public class TotalSmallSum {

    public int getSmallSum(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    private int process(int[] arr, int left, int right) {
        // base case
        if (left == right) {
            return 0;
        }
        int mid = left + ((right - left) >> 1);
        return process(arr, left, mid) +
                process(arr, mid + 1, right) +
                mergeAndCalcSmallSum(arr, left, mid, right);
    }

    private int mergeAndCalcSmallSum(int[] arr, int left, int mid, int right) {
        int[] help = new int[right - left + 1];
        int p1 = left;
        int p2 = mid + 1;
        int i = 0;

        int smallSum = 0;
        while (p1 <= mid && p2 <= right) {
            if (arr[p1] < arr[p2]) {
                help[i] = arr[p1];
                // 产生小和
                smallSum += (right - p2 + 1) * arr[p1];
                p1++;
            } else {
                // 左右相等，不产生小和，但先归并右组
                // 因为需要右组的下标计算比左边大的数的个数，必须严格大于左数
                help[i] = arr[p2];
                p2++;
            }
            i++;
        }
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= right) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[left + i] = help[i];
        }
        return smallSum;
    }
}

求数组中的逆序对个数

剑指 Offer-51 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。示例输入: [7, 5, 6, 4] 输出: 5

和上一题统计小和问题类似，我们要求的是在每一轮归并过程中，右组中有多少个数小于当前左组位置的数。

因为我们的归并排序是从小到大的，所以在右组中找小于左边的数不太好找，因为这些小的数已经被归并了，并且可能会被重复计算。

如两个数组 A[2 3 3 4], B[1 1 2 5]做归并。

当 A[0] = 2 与 B[0] = 1 比较时，是无法知道 B 中有几个元素比 A[0]小的，因为后面还有一个 1
此时 B[0] = 1 被放入新数组
当 A[0] = 2 与 B[1] = 1 比较时，也是无法知道 B 中有几个元素比 A[0]小的，除非再看向下一个
此时 B[1] = 1 被放入新数组
直到看到一个 B[2] = 2 >= A[0] = 2 时，我们才能回过头来知道，B[0] 和 B[1]两个元素小于 A[0] = 2

这个逻辑在处理 coding 细节到时候就不是很好处理了。

一种解决方法是，在归并新数组时，下标从大到小反过来填入元素；另一种思路是，要求当前右组中有多少个数小于左组，等价于当右组数固定时，求左组中有多少个数比他大。

先固定右组中的数，作为逆序对 (x, y)中的 y，那么主要找左组中有多少 x 大于 y 即可。

还是看刚才的逻辑，两个数组 A[2 3 3 4], B[1 1 2 5]做归并。

当 A[0] = 2 > B[0] = 1，那么 A[0-3]的数一定都比 B[0]大，通过下标可求得 mid - p1 + 1 = 4 个
此时 B[0] = 1 被放入新数组
当 A[0] = 2 > B[1] = 1，那么 A[0-3]的数还是都比 B[1]大，通过下标可求得 mid - p1 + 1 = 4 个
此时 B[1] = 1 被放入新数组
当 A[0] = 2 == B[2] = 2，先归并左组 A[0]，不产生逆序对
继续比较 A[1] = 3 > B[2] = 2，此时 A[1-3]的数都比 B[2]大，通过下标可求得 mid - p1 + 1 = 3 个
以此类推

因此这个算法的关键点是，在归并过程中： - 左组小于等于右组时，都先归并左组的数 - 当右组严格大于左组时，在左组中得到 mid - p1 + 1 个大于右组的数，即逆序对个数

public class O51_InversePairs {

    public int getInversePairs(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    private int process(int[] arr, int left, int right) {
        // base case
        if (left == right) {
            return 0;
        }
        int mid = left + ((right - left) >> 1);
        return process(arr, left, mid) +
                process(arr, mid + 1, right) +
                mergeAndCalcInversePairs(arr, left, mid, right);
    }

    private int mergeAndCalcInversePairs(int[] arr, int left, int mid, int right) {
        int[] help = new int[right - left + 1];
        int i = 0;
        int p1 = left;
        int p2 = mid + 1;

        int inversePair = 0;
        // 找出左组中多少数比右组大
        while (p1 <= mid && p2 <= right) {
            // 左组小于等于右组时，都先归并左组的数
            if (arr[p1] <= arr[p2]) {
                help[i++] = arr[p1++];
            } else {
                // 左组严格大于右组时，先归并右组小的数
                help[i++] = arr[p2++];
                // 同时在左组产生 p1 右边的数，都是大于右组的
                inversePair += mid - p1 + 1;
            }
        }
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= right) {
            help[i++] = arr[p2++];
        }
        // 刷回结果
        for (i = 0; i < help.length; i++) {
            arr[left + i] = help[i];
        }
        return inversePair;
    }
}

快速排序

荷兰国旗问题

给定一个数组 arr，和一个整数 num 。请把数组 L...R 上的部分按 num 划分，小于 num 的数放在数组的左边，等于的数放在中间，大于 num 的数放在数组的右边。（但左右两部分中的数不需要有序）返回等于区的左右下标。要求：num = arr[R]，额外空间复杂度 O(1)，时间复杂度 O(N)。示例：arr = [7, 1, 3, 8, 2, 5, 3, 4], L = 1, R = 6, num = arr[6] = 3 排序后： 7 [ 1 2 | 3 3 | 8 5 ] 4 返回值： [3, 4]

首先，定义两个下标分别表示小于区和大于区的界限。

int less = -1;
int larger = arr.length;

然后从左向右扫描数组，把小于的数纳入小于区，并向右推进，同时将大于的数扔到大于区，大于区向左侧逼近。最终可以得到三个区域。具体算法是：

arr[i] < num，将 arr[i] 与小于区右侧第一个数交换，less++（右扩小于区），i++（这个数搞定了）
arr[i] num，i++（先放着，继续往后看）
arr[i] > num，将 arr[i] 与大于区左侧的第一个数交换，larger--（左扩大于区）。注意此时从右边换来的数还没看过，所以 i 要停留在原地不动，下一轮再看一次。
当 index 和大于区边界撞上的时候，停止

这样随着小于区的右推，大于 num 的数被抛向大于区，而紧贴着小于区右侧的，是等于 num 的数。当整个数组扫描完成，就分为了三个部分。

public class NetherlandsFlagProblem {

    private int[] partition(int[] arr, int L, int R) {
        if (L > R) {
            return new int[] {-1, -1};
        }
        if (L == R) {
            return new int[] {L, R};
        }
        int less = L - 1;
        // 就用 arr[R] 划分，先把 arr[R] 放在大于区，最后再调整
        int larger = R;
        int i = L;
        while (i < larger) {
            if (arr[i] == arr[R]) {
                i++;
            } else if (arr[i] < arr[R]) {
                swap(arr, i++, ++less);
            } else {
                swap(arr, i, --larger);
            }
        }
        // 最后处理 arr[R]，和大于区第一个数交换
        // 这个数来到大于区第一个，真正大于区范围 [larger + 1 ... R]
        // 小于区范围 [L ... less]，等于区范围 [ less + 1, larger]
        swap(arr, larger, R);
        return new int[]{less + 1, larger};
    }

    private void swap(int[] arr, int idx1, int idx2) {
        int tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }
}

快排 1.0

快速排序的思想就基于上述的分区操作。在一次 partition 后，等于 arr[R]的数其实已经来到了目标位置，那么只需要递归的对 [L...less]和 [larger...R 范围进行 partition 操作，即可最终将整个数组排序。

private void quickSort1(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    process1(arr, 0, arr.length - 1);
}

private void process1(int[] arr, int L, int R) {
    if (L >= R) {
        return;
    }
    int[] equalArea = partition(arr, L, R);
    int less = equalArea[0];
    int larger = equalArea[1];
    process1(arr, L, less - 1);
    process1(arr, larger + 1, R);
}

这里的快排时间复杂度为 O(N^2)，因为最坏的情况，这个数组本来就是有序的，那么每次用 arr[R]做分区操作是，只能将最右边的数排好序，因此还是得做 N 轮。

快排 2.0

经典的快排算法，在上述快排的基础上，唯一的改动就是，每次 partition 不以 arr[R]来划分，而是先在 [L...R]上随机选一个数，与 arr[R]交换，然后再开始做 partition 。

为什么这样改动就可以将时间复杂度降低为

O(N \cdot \log_{}{N})

因为加入了随机 partition，最好的时间复杂度为每次都命中恰好中间，乘以概率：

T(N) = \frac{1}{N} \cdot O(N \cdot \log_{}{N})

假如每次命中 1/3 处，时间复杂度为：

T(N) = \frac{1}{N} \cdot (T(\frac{1}{3}N) + T(\frac{2}{3}N) + O(N))

若每次只命中最后一个数，时间复杂度为：

T(N) = \frac{1}{N} \cdot O(N^2)

上述每种时间复杂度出现概率都为 1/N，求数学期望，最终的时间复杂度收敛于

O(N \cdot \log_{}{N})

这就是快速排序的时间复杂度。

同理，其额外空间复杂度也是各种概率下求期望的结果，为

O(\log_{}{N})