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

分治算法实战

分治（Divide and Conquer）是解决复杂问题的核心策略，通过将大问题拆解为小问题递归求解。在 Java 中，快速排序和归并排序是分治思想的典型应用。本文将通过几个经典 LeetCode 题目，深入讲解这两种算法的变体及优化技巧。

颜色分类

题目解析：将数组中的 0、1、2 分别排列到左侧、中间和右侧。

这题可以看作双指针的进阶版。我们维护三个指针：left 指向 0 区域的右边界，right 指向 2 区域的左边界，i 用于遍历当前元素。这样数组就被分成了四部分：

• [0, left]：全是 0
• [left+1, i-1]：全是 1
• [i, right-1]：待扫描区域
• [right, n-1]：全是 2

class Solution {
    public void sortColors(int[] nums) {
        // [0,left]: 全是 0
        // [left+1,i-1]: 全是 1
        // [i,right-1]: 待扫描
        // [right,n-1]: 全是 2
        int left = -1;
        int i = 0;
        int right = nums.length;
        
        while (i < right) {
            if (nums[i] == 0) {
                swap(nums, ++left, i++);
            } else if (nums[i] == 1) {
                i++;
            } else {
                swap(nums, --right, i);
                // 交换过来的 right-1 元素尚未扫描，所以这里不能 i++
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

复杂度分析：时间复杂度 O(n)，空间复杂度 O(1)。

排序数组（快速排序）

题目解析：对给定数组进行排序。

快速排序的核心在于选择一个基准值（pivot），将数组分为小于 pivot、等于 pivot、大于 pivot 三部分，然后递归处理左右两边。为了避免最坏情况（如已排序数组），我们通常随机选择基准值。

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private void quickSort(int[] nums, int l, int r) {
        if (l >= r) return;
        
        // 随机选取基准值，避免极端情况
        int key = nums[new Random().nextInt(r - l + 1) + l];
        
        // 三向切分：[l, left] < key, [left+1, right-1] == key, [right, r] > key
        int left = l - 1;
        int right = r + 1;
        int i = l;
        
        while (i < right) {
            if (nums[i] < key) {
                swap(nums, ++left, i++);
            } else if (nums[i] == key) {
                i++;
            } else {
                swap(nums, --right, i);
            }
        }
        
        quickSort(nums, l, left);
        quickSort(nums, right, r);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

数组中第 K 个最大元素

题目解析：找出数组中第 K 大的元素。

不需要完全排序，利用快速选择的思路即可。每次分区后，判断第 K 大元素落在哪个区间，只递归处理该区间，从而将平均时间复杂度降至 O(n)。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, k);
    }

    private int quickSelect(int[] nums, int l, int r, int k) {
        if (l == r) return nums[l];
        
        int key = nums[new Random().nextInt(r - l + 1) + l];
        int left = l - 1;
        int right = r + 1;
        int i = l;
        
        while (i < right) {
            if (nums[i] < key) {
                swap(nums, ++left, i++);
            } else if (nums[i] == key) {
                i++;
            } else {
                swap(nums, --right, i);
            }
        }
        
        // 分区结果：[l, left] < key, [left+1, right-1] == key, [right, r] > key
        int b = right - left - 1; // 等于 key 的数量
        int c = r - right + 1;    // 大于 key 的数量
        
        if (c >= k) {
            return quickSelect(nums, right, r, k);
        } else if ((b + c) >= k) {
            return key;
        } else {
            return quickSelect(nums, l, left, k - b - c);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

最小的 K 个数

题目解析：返回数组中最小的 K 个数。

逻辑与上一题类似，只是关注点变成了'小于等于'的区域。同样利用快速选择的思想，只需调整一个相关模块即可。

class Solution {
    public int[] smallestK(int[] arr, int k) {
        quickSelect(arr, 0, arr.length - 1, k);
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = arr[i];
        }
        return ret;
    }

    private void quickSelect(int[] arr, int l, int r, int k) {
        if (l >= r) return;
        
        int key = arr[new Random().nextInt(r - l + 1) + l];
        int left = l - 1;
        int right = r + 1;
        int i = l;
        
        while (i < right) {
            if (arr[i] < key) {
                swap(arr, ++left, i++);
            } else if (arr[i] == key) {
                i++;
            } else {
                swap(arr, --right, i);
            }
        }
        
        // 分区：[l, left] < key, [left+1, right-1] == key, [right, r] > key
        int a = left - l + 1;
        int b = right - left - 1;
        
        if (a > k) {
            quickSelect(arr, l, left, k);
        } else if (a + b >= k) {
            return;
        } else {
            quickSelect(arr, right, r, k - a - b);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

复杂度分析：平均时间复杂度 O(n)，空间复杂度 O(k)。

排序数组（归并排序）

题目解析：使用归并思想对数组排序。

归并排序采用自顶向下的递归策略。先根据中间点将数组一分为二，分别排序，最后合并两个有序子数组。注意合并时需要辅助数组来暂存数据。

class Solution {
    private int[] temp;

    public int[] sortArray(int[] nums) {
        temp = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }

    private void mergeSort(int[] nums, int left, int right) {
        if (left >= right) return;
        
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        
        // 合并两个有序数组
        int cur1 = left;
        int cur2 = mid + 1;
        int i = 0;
        
        while (cur1 <= mid && cur2 <= right) {
            temp[i++] = nums[cur1] >= nums[cur2] ? nums[cur2++] : nums[cur1++];
        }
        
        while (cur1 <= mid) temp[i++] = nums[cur1++];
        while (cur2 <= right) temp[i++] = nums[cur2++];
        
        for (int j = left; j <= right; j++) {
            nums[j] = temp[j - left];
        }
    }
}

交易逆序对的总数

题目解析：统计满足 ai > aj 且 i < j 的逆序对数量。

在归并排序的合并阶段，当右边元素小于左边元素时，说明左边剩余的所有元素都大于该右边元素，此时可以直接累加数量。

class Solution {
    private int[] temp;

    public int reversePairs(int[] record) {
        temp = new int[record.length];
        return mergeSort(record, 0, record.length - 1);
    }

    private int mergeSort(int[] record, int left, int right) {
        if (left >= right) return 0;
        
        int mid = (left + right) / 2;
        int count = mergeSort(record, left, mid) + mergeSort(record, mid + 1, right);
        
        int cur1 = left;
        int cur2 = mid + 1;
        int i = 0;
        
        while (cur1 <= mid && cur2 <= right) {
            if (record[cur1] <= record[cur2]) {
                temp[i++] = record[cur1++];
            } else {
                // 左边剩余元素均大于右边当前元素
                count += mid - cur1 + 1;
                temp[i++] = record[cur2++];
            }
        }
        
        while (cur1 <= mid) temp[i++] = record[cur1++];
        while (cur2 <= right) temp[i++] = record[cur2++];
        
        for (int j = left; j <= right; j++) {
            record[j] = temp[j - left];
        }
        return count;
    }
}

翻转对

题目解析：统计满足 nums[i] > 2 * nums[j] 且 i < j 的对数。

与逆序对类似，但条件变为 2 倍关系。由于乘法可能溢出，建议改为除法比较 nums[i] / 2.0 <= nums[j]。此外，统计数量和合并数组需要分开进行，因为条件不同步。

class Solution {
    private int[] temp;

    public int reversePairs(int[] nums) {
        int n = nums.length;
        temp = new int[n];
        return mergeSort(nums, 0, n - 1);
    }

    private int mergeSort(int[] nums, int left, int right) {
        if (left >= right) return 0;
        
        int ret = 0;
        int mid = (left + right) / 2;
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);
        
        // 先计算翻转对数量
        int cur1 = left;
        int cur2 = mid + 1;
        while (cur1 <= mid) {
            while (cur2 <= right && nums[cur1] / 2.0 <= nums[cur2]) {
                cur2++;
            }
            if (cur2 > right) break;
            ret += right - cur2 + 1;
            cur1++;
        }
        
        // 再合并有序数组
        cur1 = left;
        cur2 = mid + 1;
        int i = left;
        while (cur1 <= mid && cur2 <= right) {
            temp[i++] = nums[cur1] >= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        while (cur1 <= mid) temp[i++] = nums[cur1++];
        while (cur2 <= right) temp[i++] = nums[cur2++];
        
        for (int j = left; j <= right; j++) {
            nums[j] = temp[j - left];
        }
        return ret;
    }
}

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

题目解析：返回新数组，每个位置的值表示原数组中该位置右侧比它小的元素个数。

归并排序过程中，我们可以知道右侧有多少元素被移到了左侧前面。但由于排序会打乱原始顺序，我们需要额外维护一个索引数组 index，记录每个元素原本的下标，以便更新结果。

class Solution {
    private int[] ret;
    private int[] index;
    private int[] tempIndex;
    private int[] tempNums;

    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        ret = new int[n];
        index = new int[n];
        tempIndex = new int[n];
        tempNums = new int[n];
        
        for (int i = 0; i < n; i++) {
            index[i] = i;
        }
        
        mergeSort(nums, 0, n - 1);
        
        List<Integer> result = new ArrayList<>();
        for (int x : ret) {
            result.add(x);
        }
        return result;
    }

    private void mergeSort(int[] nums, int left, int right) {
        if (left >= right) return;
        
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        
        int cur1 = left;
        int cur2 = mid + 1;
        int i = 0;
        
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] <= nums[cur2]) {
                tempNums[i] = nums[cur2];
                tempIndex[i++] = index[cur2++];
            } else {
                // 右侧元素小于左侧，更新对应下标的计数
                ret[index[cur1]] += right - cur2 + 1;
                tempNums[i] = nums[cur1];
                tempIndex[i++] = index[cur1++];
            }
        }
        
        while (cur1 <= mid) {
            tempNums[i] = nums[cur1];
            tempIndex[i++] = index[cur1++];
        }
        while (cur2 <= right) {
            tempNums[i] = nums[cur2];
            tempIndex[i++] = index[cur2++];
        }
        
        for (int j = left; j <= right; j++) {
            nums[j] = tempNums[j - left];
            index[j] = tempIndex[j - left];
        }
    }
}