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

Javajava算法

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

基于分治思想的 Java 算法题练习，涵盖快速排序和归并排序的应用。内容包括颜色分类、排序数组、第 K 大元素、最小 K 个数、逆序对及翻转对等经典问题。通过随机基准值优化快排性能，利用归并过程统计逆序对数量，并解决右侧小元素计数问题。文章提供了完整的 Java 代码实现及复杂度分析，适合算法进阶学习。

落日余晖发布于 2026/3/30更新于 2026/4/131 浏览

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

分治算法

使用快速排序和归并排序解决问题，因为这两个都是采用分治的思想。

颜色分类

题目解析：将数组中 0 放在左边，1 放在中间，2 放在右边。在双指针算法中有一个移动零的题目，就是将所有 0 元素移动到右边，但是非 0 元素相对位置不改变。那题使用双指针将其数组分为三部分，因此这题也可以将其数组分块。left 表示为 0 区域最右侧，i 遍历数组，right 表示 2 区域最左侧。使用这三个指针将这个数组分为了 4 部分。

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 下标，但是这个元素没有扫描过，所以这里不可以让 i++
            }
        }
    }

    public void swap(int[] nums, int i, int j) {
        int tem = nums[i];
        nums[i] = nums[j];
        nums[j] = tem;
    }
}

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

Keycode 信息
查找任何按下的键的javascript键代码、代码、位置和修饰符。在线工具，Keycode 信息在线工具，online
Escape 与 Native 编解码
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。在线工具，Escape 与 Native 编解码在线工具，online
JavaScript / HTML 格式化
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。在线工具，JavaScript / HTML 格式化在线工具，online
JavaScript 压缩与混淆
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。在线工具，JavaScript 压缩与混淆在线工具，online
加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online

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

    public void qsort(int[] nums, int l, int r) {
        if (l >= r) {
            return;
        }
        // 这里采用随机获取 key
        // 随机的下标是 [l,r];
        int key = nums[new Random().nextInt(r - l + 1) + l];
        // 这里根据 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);
            }
        }
        qsort(nums, l, left);
        qsort(nums, right, r);
    }

    public void swap(int[] nums, int i, int j) {
        int tem = nums[i];
        nums[i] = nums[j];
        nums[j] = tem;
    }
}

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

    public 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] [left+1,right-1] [right,r]
        // 判断其第 k 大的元素在那个模块
        int b = right - left - 1;
        int c = r - right + 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);
        }
    }

    public void swap(int[] nums, int i, int j) {
        int tem = nums[i];
        nums[i] = nums[j];
        nums[j] = tem;
    }
}

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;
    }

    public 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);
            }
        }
        // [l,left] [left + 1, right - 1],[right , r]
        int a = left - l + 1;
        int b = right - left - 1;
        if (a > k) {
            qsort(arr, l, left, k);
        } else if (a + b >= k) {
            return;
        } else {
            qsort(arr, right, r, k - a - b);
        }
    }

    public void swap(int[] arr, int i, int j) {
        int tem = arr[i];
        arr[i] = arr[j];
        arr[j] = tem;
    }
}

class Solution {
    int[] temp;

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

    public 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];
        }
    }
}

// 升序
class Solution {
    int[] temp;

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

    public 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]) {
                // cur1 向后走，此时没有
                temp[i++] = record[cur1++];
            } else {
                ret += 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 ret;
    }
}

// 降序
class Solution {
    // 降序就是找后面又几个数比我小
    int[] temp;

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

    public 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]) {
                // cur1 向后走，此时没有
                temp[i++] = record[cur2++];
            } else {
                ret += right - cur2 + 1;
                temp[i++] = record[cur1++];
            }
        }
        // 处理还没有遍历完的数组
        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 ret;
    }
}

// 降序
class Solution {
    int[] temp;

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

    public 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];
        }
        return ret;
    }
}

// 升序
class Solution {
    int[] temp;

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

    public 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 (cur2 <= right) {
            while (cur1 <= mid && nums[cur1] / 2.0 <= nums[cur2]) {
                cur1++;
            }
            if (cur1 > mid) {
                break;
            }
            // 更新结果
            ret += mid - cur1 + 1;
            cur2++;
        }
        // 合并两个有序数组
        cur1 = left;
        cur2 = mid + 1;
        int i = left;
        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];
        }
        return ret;
    }
}

class Solution {
    int[] ret; // 返回结果
    int[] index; // 对应下标
    int[] tempIndex;
    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> l = new ArrayList<>();
        for (int x : ret) {
            l.add(x);
        }
        return l;
    }

    public 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 {
                // 更新结果，此时找到 cur1 对应的下标进行赋值
                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];
        }
    }
}