本文详解如何用 java 正确实现 hoare 版快速排序，并解决常见输出问题——包括修复分区逻辑缺陷、补全排序调用、以及规范打印数组结果。
本文详解如何用 java 正确实现 hoare 版快速排序，并解决常见输出问题——包括修复分区逻辑缺陷、补全排序调用、以及规范打印数组结果。
快速排序（Quick Sort）是经典的分治排序算法，而 Hoare 分区方案以其高效性和原地交换特性被广泛采用。但初学者常因边界处理不当或调用缺失导致排序失败，且容易忽略结果可视化——例如示例中 System.out.println("Hoare's quicksort: " + test1) 仅打印数组对象引用（如 [I@xxxxx），而非实际内容。
✅ 关键问题修复与优化
1. 修复 Hoare 分区逻辑
原始 partitionHoare 存在两处关键缺陷：
- 越界风险：do-while 循环未校验 i 和 j 是否越界，可能导致 IndexOutOfBoundsException；
- 降序逻辑错误：注释称“按降序排序”，但比较逻辑 compareTo(pivot) > 0 实际实现的是升序（因 a.compareTo(b) > 0 表示 a > b，故 list.get(i) > pivot 时继续右移 i，符合升序分区）；若需降序，应反转比较符号。
修正后的分区方法如下（含越界防护与清晰注释）：
public static <E extends Comparable<E>> int partitionHoare(ArrayList<E> list, int l, int r) {
E pivot = list.get(l);
int i = l - 1;
int j = r + 1;
while (true) {
// 向右找第一个 ≤ pivot 的元素（升序：左侧应 ≤ pivot）
do {
i++;
if (i > r) break; // 防越界
} while (list.get(i).compareTo(pivot) < 0);
// 向左找第一个 ≥ pivot 的元素（升序：右侧应 ≥ pivot）
do {
j--;
if (j < l) break; // 防越界
} while (list.get(j).compareTo(pivot) > 0);
if (i >= j) {
return j;
}
// 交换不满足条件的元素
E temp = list.get(i);
list.set(i, list.get(j));
list.set(j, temp);
}
}2. 补全排序调用与结果验证
主方法中仅创建列表却未执行排序，且 test1 是原始数组，未反映排序结果。需：
Alibabacloud Sdk Client Initialization For Java
下载
在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。
立即学习“Java免费学习笔记（深入）”；
- 调用 quicksortHoare(list1, 0, list1.size() - 1)；
- 使用 Arrays.toString() 打印原始数组（test1）或转换为数组后打印排序结果。
public static void main(String[] args) {
int[] test1 = {3, 5, 2, 4, 1, 8, 7, 6, 9};
ArrayList<Integer> list1 = new ArrayList<>();
for (int num : test1) {
list1.add(num);
}
System.out.println("*** Test 1 ***");
System.out.println("Original list: " + list1);
// ✅ 执行 Hoare 快速排序（升序）
quicksortHoare(list1, 0, list1.size() - 1);
// ✅ 正确打印：使用 Arrays.toString() 显示数组内容
System.out.println("Sorted list: " + list1); // ArrayList 可直接打印
// 若需打印对应数组：System.out.println("Sorted array: " + Arrays.toString(list1.toArray(new Integer[0])));
}3. 注意事项与最佳实践
- 泛型约束：<E extends Comparable<E>> 已确保元素可比较，无需额外检查；
- 递归终止条件：if (l < r) 正确，避免单元素或空区间递归；
- 性能提示：Hoare 分区交换次数更少，但最坏时间复杂度仍为 O(n²)，建议随机化 pivot 或改用三数取中法提升稳定性；
- 输出规范：永远避免直接 System.out.println(array) —— 必须使用 Arrays.toString(array)（一维基本类型数组）或 Arrays.deepToString()（多维数组）。
运行修正后代码，输出将清晰显示：
*** Test 1 *** Original list: [3, 5, 2, 4, 1, 8, 7, 6, 9] Sorted list: [1, 2, 3, 4, 5, 6, 7, 8, 9]
掌握 Hoare 分区的核心在于理解双向扫描与边界守卫，辅以严谨的测试输出，方能写出健壮、可验证的排序实现。
