分治算法实战：快速排序与归并排序详解

2. 排序数组

题目链接： LeetCode 912 - 排序数组

思路解析： 在处理包含大量重复数据的场景下，三路划分能显著提升效率。我们需要随机选择基准值以避免最坏情况。

关键步骤：

1. 设置随机数种子；
2. 生成随机下标作为基准；
3. 利用三路划分将数组划分为三个区域；
4. 递归处理左边和右边区域。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        srand(time(NULL));
        qsort(nums, 0, nums.size() - 1);
        return nums;
    }

    void qsort(vector<int>& nums, int l, int r) {
        if (l >= r) return;
        int key = getRandom(nums, l, r);
        int left = l - 1, right = r + 1, cur = l;
        while (cur < right) {
            if (nums[cur] < key) swap(nums[++left], nums[cur++]);
            else if (nums[cur] == key) cur++;
            else swap(nums[--right], nums[cur]);
        }
        qsort(nums, l, left);
        qsort(nums, right, r);
    }

    int getRandom(vector<int>& nums, int l, int r) {
        int e = rand();
        return nums[e % (r - l + 1) + l];
    }
};

3. 数组中的第 K 个最大元素

题目链接： LeetCode 215 - 第 K 个最大元素

思路解析： 快排分区后，我们可以计算每个区间元素的个数，推断目标元素落在哪个区间，然后只在相应区间继续查找。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return qsort(nums, 0, nums.size() - 1, k);
    }

    int qsort(vector<int>& nums, int l, int r, int k) {
        if (l == r) return nums[l];
        int key = getRandom(nums, l, r);
        int left = l - 1, right = r + 1, cur = l;
        while (cur < right) {
            if (nums[cur] < key) swap(nums[++left], nums[cur++]);
            else if (nums[cur] == key) cur++;
            else swap(nums[--right], nums[cur]);
        }
        int c = r - right + 1, b = right - 1 - (left + 1) + 1;
        if (c >= k) return qsort(nums, right, r, k);
        else if (b + c >= k) return key;
        else return qsort(nums, l, left, k - b - c);
    }

    int getRandom(vector<int>& nums, int l, int r) {
        return nums[rand() % (r - l + 1) + l];
    }
};

4. 最小 K 个数

题目链接： LeetCode LCCI - 最小 K 个数

思路解析： 与寻找第 K 大元素类似，区别在于在小元素区间内寻找。找到前 K 小的元素即可返回。

class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        srand(time(NULL));
        qsort(arr, 0, arr.size() - 1, k);
        return {arr.begin(), arr.begin() + k};
    }

    void qsort(vector<int>& arr, int l, int r, int k) {
        if (l >= r) return;
        int key = getRandom(arr, l, r);
        int left = l - 1, right = r + 1, cur = l;
        while (cur < right) {
            if (arr[cur] < key) swap(arr[++left], arr[cur++]);
            else if (arr[cur] == key) cur++;
            else swap(arr[--right], arr[cur]);
        }
        int a = left - l + 1, b = right - 1 - (left + 1) + 1;
        if (a > k) qsort(arr, l, left, k);
        else if (a + b >= k) return;
        else qsort(arr, right, r, k - a - b);
    }

    int getRandom(vector<int>& arr, int l, int r) {
        return arr[rand() % (r - l + 1) + l];
    }
};

二、归并排序（Merge Sort）

归并排序完美体现了【分而治之】的思想：先递归分解到长度为 1，再合并有序数组。

1. 排序数组

思路解析：

1. 分：取中点，将数组一分为二；
2. 治：合并两个较短的有序数组。

class Solution {
    vector<int> tmp;
public:
    vector<int> sortArray(vector<int>& nums) {
        tmp.resize(nums.size());
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }

    void mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) return;
        int mid = (right + left) >> 1;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right) {
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        while (cur1 <= mid) tmp[i++] = nums[cur1++];
        while (cur2 <= right) tmp[i++] = nums[cur2++];
        for (int i = left; i <= right; i++) nums[i] = tmp[i - left];
    }
};

2. 交易逆序对的总数

题目链接： LeetCode LCOF - 数组中的逆序对

思路解析： 利用归并排序合并过程统计逆序对。将逆序对来源分为三类：全在左半部分、全在右半部分、一个在左一个在右。关键在于合并时利用有序性快速统计跨区间的逆序对。

方法一：统计某个数前面有多少个数比它大 合并升序数组时，若 left[cur1] > right[cur2]，则 left 中剩余所有元素均构成逆序对。

方法二：统计某个数后面有多少个数比它小 合并升序数组时，若 left[cur1] <= right[cur2]，则 right 中已遍历过的元素均比 left[cur1] 小。

// 升序版本
class Solution {
    int tmp[50001];
public:
    int reversePairs(vector<int>& record) {
        return mergeSort(record, 0, record.size() - 1);
    }

    int mergeSort(vector<int>& record, int left, int right) {
        if (left >= right) return 0;
        int ret = 0;
        int mid = (left + right) >> 1;
        ret += mergeSort(record, left, mid);
        ret += mergeSort(record, mid + 1, right);

        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right) {
            if (record[cur1] <= record[cur2]) tmp[i++] = record[cur1++];
            else {
                ret += mid - cur1 + 1;
                tmp[i++] = record[cur2++];
            }
        }
        while (cur1 <= mid) tmp[i++] = record[cur1++];
        while (cur2 <= right) tmp[i++] = record[cur2++];
        for (int i = left; i <= right; i++) record[i] = tmp[i - left];
        return ret;
    }
};

3. 计算右侧小于当前元素的个数

题目链接： LeetCode 315 - 计算右侧小于当前元素的个数

思路解析： 不同于求总数，本题需返回每个元素对应的计数。由于归并排序会打乱下标，我们需要绑定元素与其原始下标。利用降序归并的特性，当 nums[cur1] > nums[cur2] 时，说明 nums[cur1] 比右侧已处理的所有元素都大。

class Solution {
public:
    vector<int> counts;
    vector<int> index;
    int tmpNum[100001];
    int tmpIndex[100001];

    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        counts.resize(n);
        index.resize(n);
        for (int i = 0; i < n; i++) index[i] = i;
        mergeSort(nums, 0, n - 1);
        return counts;
    }

    void mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) return;
        int mid = (left + right) >> 1;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] <= nums[cur2]) {
                tmpNum[i] = nums[cur2];
                tmpIndex[i++] = index[cur2++];
            } else {
                counts[index[cur1]] += right - cur2 + 1;
                tmpNum[i] = nums[cur1];
                tmpIndex[i++] = index[cur1++];
            }
        }
        while (cur1 <= mid) { tmpNum[i] = nums[cur1]; tmpIndex[i++] = index[cur1++]; }
        while (cur2 <= right) { tmpNum[i] = nums[cur2]; tmpIndex[i++] = index[cur2++]; }
        for (int i = left; i <= right; i++) {
            nums[i] = tmpNum[i - left];
            index[i] = tmpIndex[i - left];
        }
    }
};

4. 翻转对

题目链接： LeetCode 493 - 翻转对

思路解析： 翻转对定义为 i < j 且 nums[i] > 2 * nums[j]。与逆序对类似，但条件更严格。由于涉及倍数关系，不能直接在合并时统计，需在合并前单独统计一次。

使用双指针扫描两个有序子数组：对于 left[cur1]，移动 cur2 直到 left[cur1] <= 2 * right[cur2]，此时 right 中 cur2 之前的元素均满足条件。

// 降序版本
class Solution {
public:
    int tmp[50001];
    int reversePairs(vector<int>& nums) {
        return mergeSort(nums, 0, nums.size() - 1);
    }

    int mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) return 0;
        int ret = 0;
        int mid = (left + right) >> 1;
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);

        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid) {
            while (cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;
            if (cur2 > right) break;
            ret += right - cur2 + 1;
            cur1++;
        }

        cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right) {
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];
        }
        while (cur1 <= mid) tmp[i++] = nums[cur1++];
        while (cur2 <= right) tmp[i++] = nums[cur2++];
        for (int i = left; i <= right; i++) nums[i] = tmp[i - left];
        return ret;
    }
};