SilverLining's Blog

归并排序与快排序

归并排序

传统的数组排序算法时间复杂度是 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]做归并。

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

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

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

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

因此这个算法的关键点是,在归并过程中: - 左组小于等于右组时,都先归并左组的数 - 当右组严格大于左组时,在左组中得到 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;

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

这样随着小于区的右推,大于 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})