Java 分治算法实战：快速排序与归并排序 | 极客日志

Javajava算法

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

基于 Java 语言，深入探讨分治算法在快速排序、归并排序及相关变体问题中的应用。涵盖颜色分类、数组排序、第 K 大元素、逆序对计数及右侧小于当前元素个数等经典场景。重点解析三路快排优化、随机基准值选取、归并排序中的统计技巧以及索引映射处理，提供完整可运行的代码示例与复杂度分析。

剑仙发布于 2026/3/270 浏览

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

Java 分治算法实战

分治思想是算法设计中的核心范式之一，通过递归地将大问题拆解为小问题来解决。在排序领域，快速排序和归并排序是最经典的两个应用。本文将结合 LeetCode 上的经典题目，深入剖析这两种算法的实现细节、优化策略以及变体应用。

1. 颜色分类

题目链接： 颜色分类

颜色分类示意图

这道题要求将数组中的 0、1、2 分别排在左侧、中间和右侧。这其实是荷兰国旗问题的变种。我们可以借鉴双指针中'移动零'的思路，将数组划分为三个区域：

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

使用 left、i、right 三个指针进行遍历。当遇到 0 时，交换到左侧；遇到 2 时，交换到右侧（注意此时 right 指向的元素未扫描，不能移动 i）；遇到 1 则直接跳过。

class Solution {
    public void sortColors(int[] nums) {
        // 初始化指针
        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 {
                // 遇到 2，交换到右侧，但 right-1 处的元素尚未检查，所以 i 不增加
                swap(nums, --right, i);
            }
        }
    }

       {
           nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

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

    private void qsort(int[] nums, int l, int r) {
        if (l >= r) {
            return;
        }
        // 随机选取基准值，避免最坏情况
        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);
            }
        }
        
        qsort(nums, l, left);
        qsort(nums, right, r);
    }

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

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

    private int qsort(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) {
            // 目标在右侧大于 key 的区域
            return qsort(nums, right, r, k);
        } else if ((b + c) >= k) {
            // 目标就是 key
            return key;
        } else {
            // 目标在左侧小于 key 的区域，需减去右侧数量
            return qsort(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;
    }
}

class Solution {
    public int[] smallestK(int[] arr, int k) {
        qsort(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 qsort(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);
            }
        }
        
        int a = left - l + 1;      // 小于 key 的数量
        int b = right - left - 1;  // 等于 key 的数量
        
        if (a > k) {
            qsort(arr, l, left, k);
        } else if (a + b >= k) {
            return;
        } else {
            qsort(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;
    }
}

class Solution {
    int[] tem;

    public int[] sortArray(int[] nums) {
        tem = 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) {
            tem[i++] = nums[cur1] >= nums[cur2] ? nums[cur2++] : nums[cur1++];
        }
        
        while (cur1 <= mid) {
            tem[i++] = nums[cur1++];
        }
        while (cur2 <= right) {
            tem[i++] = nums[cur2++];
        }
        
        for (int j = left; j <= right; j++) {
            nums[j] = tem[j - left];
        }
    }
}

class Solution {
    int[] tem;

    public int reversePairs(int[] record) {
        tem = 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 ret = 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]) {
                tem[i++] = record[cur1++];
            } else {
                // 发现逆序对
                ret += mid - cur1 + 1;
                tem[i++] = record[cur2++];
            }
        }
        
        while (cur1 <= mid) {
            tem[i++] = record[cur1++];
        }
        while (cur2 <= right) {
            tem[i++] = record[cur2++];
        }
        
        for (int j = left; j <= right; j++) {
            record[j] = tem[j - left];
        }
        return ret;
    }
}

class Solution {
    int[] tem;

    public int reversePairs(int[] nums) {
        int n = nums.length;
        tem = 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) {
            tem[i++] = nums[cur1] >= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        while (cur1 <= mid) {
            tem[i++] = nums[cur1++];
        }
        while (cur2 <= right) {
            tem[i++] = nums[cur2++];
        }
        for (int j = left; j <= right; j++) {
            nums[j] = tem[j];
        }
        return ret;
    }
}

class Solution {
    int[] ret;
    int[] index;
    int[] temIndex;
    int[] temNums;

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

    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]) {
                temNums[i] = nums[cur2];
                temIndex[i++] = index[cur2++];
            } else {
                // 更新结果，此时 cur1 对应的下标后面有 right - cur2 + 1 个比它小的数
                ret[index[cur1]] += right - cur2 + 1;
                temNums[i] = nums[cur1];
                temIndex[i++] = index[cur1++];
            }
        }
        
        while (cur1 <= mid) {
            temNums[i] = nums[cur1];
            temIndex[i++] = index[cur1++];
        }
        while (cur2 <= right) {
            temNums[i] = nums[cur2];
            temIndex[i++] = index[cur2++];
        }
        
        for (int j = left; j <= right; j++) {
            nums[j] = temNums[j - left];
            index[j] = temIndex[j - left];
        }
    }
}