引言
分治（Divide and Conquer）是算法设计的四大核心思想之一，它与动态规划、贪心策略、回溯搜索共同构成了算法问题求解的基石。归并排序和快速排序是分治策略最经典的两个范例，本文将用 Java 深入剖析这两种排序算法的实现细节，提炼出分治策略的统一解题框架，并展示如何利用该框架解决逆序对计数等经典问题。
分治策略的核心思想
分治策略遵循”分而治之”的哲学，将一个大问题分解为若干个相互独立、结构相似的子问题，递归求解子问题，然后将子问题的解合并为原问题的解。分治算法的执行流程包含三个关键步骤：
- 分解（Divide）：将原问题划分为若干个规模更小、结构相似的子问题
- 解决（Conquer）：递归地求解各个子问题。若子问题规模足够小，则直接求解
- 合并（Merge）：将子问题的解合并为原问题的解
归并排序：稳定分治的典范
算法思想
归并排序将数组从中间分成两半，递归地对左右两半分别排序，然后将两个有序子数组合并为一个有序数组。合并过程是归并排序的核心，也是其稳定性的来源。
算法实现
import java.util.Arrays;
/**
* 归并排序实现
* 时间复杂度：O(n log n) — 稳定，最坏、最好、平均情况一致
* 空间复杂度：O(n) — 需要额外数组存储合并结果
*/
public class MergeSort {
/**
* 归并排序入口
*
* @param nums 待排序数组
*/
public void sort(int[] nums) {
if (nums == null || nums.length <= 1) {
return;
}
// 使用临时数组避免递归过程中频繁创建数组
int[] temp = new int[nums.length];
mergeSort(nums, 0, nums.length - 1, temp);
}
/**
* 递归分解并排序
*
* @param nums 原数组
* @param left 当前区间的左边界
* @param right 当前区间的右边界
* @param temp 临时数组，用于合并
*/
private void mergeSort(int[] nums, int left, int right, int[] temp) {
// 递归终止条件：区间只有一个元素，天然有序
if (left >= right) {
return;
}
// 分解：将当前区间从中间分成两半
int mid = left + (right - left) / 2; // 防止整数溢出的写法
// 递归排序左半部分 [left, mid]
mergeSort(nums, left, mid, temp);
// 递归排序右半部分 [mid+1, right]
mergeSort(nums, mid + 1, right, temp);
// 合并：将两个有序子数组合并
merge(nums, left, mid, right, temp);
}
/**
* 合并两个有序子数组：nums[left..mid] 和 nums[mid+1..right]
*
* @param nums 原数组
* @param left 左子数组起始位置
* @param mid 左子数组结束位置（右子数组起始位置为 mid+1）
* @param right 右子数组结束位置
* @param temp 临时数组
*/
private void merge(int[] nums, int left, int mid, int right, int[] temp) {
// 将待合并的数据复制到临时数组
for (int i = left; i <= right; i++) {
temp[i] = nums[i];
}
int i = left; // 左子数组指针
int j = mid + 1; // 右子数组指针
int k = left; // 结果数组指针
// 比较左右子数组的元素，将较小者放入结果数组
while (i <= mid && j <= right) {
if (temp[i] <= temp[j]) {
nums[k++] = temp[i++];
} else {
nums[k++] = temp[j++];
}
}
// 处理左子数组剩余元素
while (i <= mid) {
nums[k++] = temp[i++];
}
// 处理右子数组剩余元素
while (j <= right) {
nums[k++] = temp[j++];
}
}
}
归并排序的关键特性
- 稳定性：相等元素的相对顺序在排序前后保持不变。这得益于合并时
temp[i] <= temp[j]的取等策略，优先取左侧元素 - 非原地排序：需要 O(n) 的额外空间
- 时间复杂度稳定：无论输入数据如何分布，时间复杂度始终为 O(n log n)
快速排序：高效分治的代表
算法思想
快速排序选择一个基准元素（pivot），通过一趟排序将数组分为两部分：左边所有元素小于等于 pivot，右边所有元素大于 pivot。然后递归地对左右两部分进行快速排序。
算法实现
/**
* 快速排序实现
* 时间复杂度：平均 O(n log n)，最坏 O(n²)（数组已有序时）
* 空间复杂度：O(log n) — 递归栈空间
*/
public class QuickSort {
/**
* 快速排序入口
*
* @param nums 待排序数组
*/
public void sort(int[] nums) {
if (nums == null || nums.length <= 1) {
return;
}
quickSort(nums, 0, nums.length - 1);
}
/**
* 递归快速排序
*
* @param nums 待排序数组
* @param left 当前区间左边界
* @param right 当前区间右边界
*/
private void quickSort(int[] nums, int left, int right) {
// 递归终止条件
if (left >= right) {
return;
}
// 分区：将数组分为两部分，返回 pivot 的最终位置
int pivotIndex = partition(nums, left, right);
// 递归排序左半部分（不包括 pivot）
quickSort(nums, left, pivotIndex - 1);
// 递归排序右半部分（不包括 pivot）
quickSort(nums, pivotIndex + 1, right);
}
/**
* 分区操作：选择最右元素作为 pivot，将数组分为 <pivot 和 >=pivot 两部分
*
* @param nums 待分区数组
* @param left 分区区间左边界
* @param right 分区区间右边界（pivot 位置）
* @return pivot 的最终位置
*/
private int partition(int[] nums, int left, int right) {
int pivot = nums[right]; // 选择最右元素作为 pivot
int i = left; // i 指向小于 pivot 的区域的下一个位置
for (int j = left; j < right; j++) {
if (nums[j] < pivot) {
// 发现小于 pivot 的元素，将其交换到区域前端
swap(nums, i, j);
i++;
}
}
// 将 pivot 放到正确的位置（小于 pivot 的元素都在其左侧）
swap(nums, i, right);
return i; // 返回 pivot 的最终位置
}
/**
* 三数取中法优化分区
* 选择 left、mid、right 三个位置的中位数作为 pivot，避免最坏情况
*/
private int medianOfThree(int[] nums, int left, int right) {
int mid = left + (right - left) / 2;
// 将三个数中的中位数放到 right 位置
if (nums[left] > nums[mid]) {
swap(nums, left, mid);
}
if (nums[left] > nums[right]) {
swap(nums, left, right);
}
if (nums[mid] > nums[right]) {
swap(nums, mid, right);
}
// 将中位数放到 right-1 位置（或直接返回 mid）
swap(nums, mid, right);
return partition(nums, left, right);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
双路快排优化
对于包含大量重复元素的数组，普通快排会退化为 O(n²)。双路快排将数组分为 < pivot 和 > pivot 两部分，将等于 pivot 的元素均匀分布在两边。
/**
* 双路快排分区：处理大量重复元素的情况
*
* @param nums 待分区数组
* @param left 左边界
* @param right 右边界
* @return pivot 的索引范围（这里返回左分区的结束位置）
*/
private int partition2Way(int[] nums, int left, int right) {
// 随机选择 pivot 避免最坏情况
int randomIndex = left + (int)(Math.random() * (right - left + 1));
swap(nums, left, randomIndex);
int pivot = nums[left];
int i = left + 1; // [left+1, i) <= pivot
int j = right; // (j, right] >= pivot
while (true) {
// i 从左向右找第一个 >= pivot 的元素
while (i <= j && nums[i] < pivot) i++;
// j 从右向左找第一个 <= pivot 的元素
while (i <= j && nums[j] > pivot) j--;
if (i > j) break;
swap(nums, i, j);
i++;
j--;
}
// 将 pivot 放到正确位置
swap(nums, left, j);
return j;
}
分治统一框架
从归并排序和快速排序中，我们可以提炼出分治策略的统一解题框架：
/**
* 分治策略统一框架
*
* @param problem 当前要解决的问题/数据
* @return 问题的解
*/
public Result divideAndConquer(Problem problem) {
// 1. 递归终止条件：问题规模足够小，直接求解
if (problem.isBaseCase()) {
return problem.solveDirectly();
}
// 2. 分解：将问题划分为若干子问题
List<Problem> subProblems = problem.divide();
// 3. 解决：递归求解各个子问题
List<Result> subResults = new ArrayList<>();
for (Problem sub : subProblems) {
subResults.add(divideAndConquer(sub));
}
// 4. 合并：将子问题的解合并为原问题的解
return problem.merge(subResults);
}
归并排序 vs 快速排序的分治对比
| 特性 | 归并排序 | 快速排序 |
|---|---|---|
| 分解方式 | 固定中点，均等二分 | 按 pivot 值分区，大小不确定 |
| 主要工作 | 合并过程复杂，分解简单 | 分区过程复杂，合并简单（无需合并） |
| 稳定性 | 稳定 | 不稳定 |
| 空间复杂度 | O(n) | O(log n) |
| 最坏时间复杂度 | O(n log n) | O(n²) |
| 适用场景 | 需要稳定排序、链表排序 | 通用场景、追求原地排序 |
经典应用：逆序对计数
逆序对是指数组中满足 i < j 且 nums[i] > nums[j] 的元素对。利用归并排序的合并过程，可以在 O(n log n) 时间内统计逆序对数量。
/**
* 逆序对计数 — 基于归并排序的分治解法
* 核心思想：在合并两个有序子数组时，若左子数组当前元素大于右子数组当前元素，
* 则左子数组剩余所有元素都与该右子数组元素构成逆序对
* 时间复杂度：O(n log n)
* 空间复杂度：O(n)
*/
public class InversionCount {
private long inversionCount; // 逆序对总数（可能很大，用 long）
/**
* 统计数组中的逆序对数量
*
* @param nums 待统计数组
* @return 逆序对数量
*/
public long count(int[] nums) {
if (nums == null || nums.length <= 1) {
return 0;
}
inversionCount = 0;
int[] temp = new int[nums.length];
mergeSortAndCount(nums, 0, nums.length - 1, temp);
return inversionCount;
}
private void mergeSortAndCount(int[] nums, int left, int right, int[] temp) {
if (left >= right) {
return;
}
int mid = left + (right - left) / 2;
// 递归统计左右子数组的逆序对
mergeSortAndCount(nums, left, mid, temp);
mergeSortAndCount(nums, mid + 1, right, temp);
// 合并并统计跨区间的逆序对
mergeAndCount(nums, left, mid, right, temp);
}
private void mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
for (int i = left; i <= right; i++) {
temp[i] = nums[i];
}
int i = left; // 左子数组指针
int j = mid + 1; // 右子数组指针
int k = left; // 结果数组指针
while (i <= mid && j <= right) {
if (temp[i] <= temp[j]) {
nums[k++] = temp[i++];
} else {
// 关键：temp[i] > temp[j]，说明 temp[i..mid] 都大于 temp[j]
// 这些元素都与 temp[j] 构成逆序对
inversionCount += (mid - i + 1);
nums[k++] = temp[j++];
}
}
while (i <= mid) {
nums[k++] = temp[i++];
}
while (j <= right) {
nums[k++] = temp[j++];
}
}
}
逆序对计数的原理分析
在归并排序的合并阶段，左右两个子数组已经分别有序。当左子数组的当前元素 temp[i] 大于右子数组的当前元素 temp[j] 时，由于左子数组有序，temp[i] 及其之后的所有元素（共 mid - i + 1 个）都大于 temp[j]，因此都与 temp[j] 构成逆序对。
完整测试代码
public class DivideAndConquerDemo {
public static void main(String[] args) {
// 归并排序测试
int[] arr1 = {5, 2, 8, 1, 9, 3, 7, 4, 6};
System.out.println("归并排序前: " + Arrays.toString(arr1));
new MergeSort().sort(arr1);
System.out.println("归并排序后: " + Arrays.toString(arr1));
// 快速排序测试
int[] arr2 = {5, 2, 8, 1, 9, 3, 7, 4, 6};
System.out.println("\n快速排序前: " + Arrays.toString(arr2));
new QuickSort().sort(arr2);
System.out.println("快速排序后: " + Arrays.toString(arr2));
// 逆序对计数测试
int[] arr3 = {7, 5, 6, 4};
InversionCount ic = new InversionCount();
long count = ic.count(arr3.clone());
System.out.println("\n数组 [7, 5, 6, 4] 的逆序对数量: " + count); // 应为 5
// 大规模数据测试
int[] largeArr = new int[100000];
for (int i = 0; i < largeArr.length; i++) {
largeArr[i] = largeArr.length - i; // 完全逆序
}
long start = System.currentTimeMillis();
long invCount = ic.count(largeArr.clone());
long end = System.currentTimeMillis();
System.out.println("\n100000 个逆序元素的逆序对数量: " + invCount);
System.out.println("计算耗时: " + (end - start) + " ms");
}
}
复杂度分析
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 逆序对计数 | O(n log n) | O(n log n) | O(n) | – |
总结
归并排序和快速排序是分治策略的两大典范。归并排序的”先分后合”思路强调合并过程的复杂性，保证了稳定性和时间复杂度的稳定性；快速排序的”先治后分”思路将主要工作放在分区过程，追求原地排序的高效性。通过对比这两种算法，我们能够深刻理解分治策略中”分解”与”合并”的权衡艺术。
逆序对计数展示了分治策略的强大扩展性——在归并排序的框架中嵌入计数逻辑，即可在相同的时间复杂度内解决一个看似不相关的问题。掌握分治的统一框架，培养”能否将问题分解为相似子问题”的思维习惯，是提升算法设计能力的关键一步。
