快速排序（quicksort）是一种高效的、基于比较的排序算法，其核心思想是“分而治之”（divide and conquer）。它通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，最终使整个数据序列有序。
快速排序的关键在于“分区”操作。常见的分区方案有两种：Lomuto 分区和 Hoare 分区。本教程将重点介绍 Hoare 分区方案的实现。
Hoare 分区方案是快速排序的原始设计，它通常比 Lomuto 分区更高效，因为它执行的交换次数更少。Hoare 分区的基本思想是：
这种分区方式将数组分为两部分，枢轴本身可能不在最终的 j 位置，但 j 位置是枢轴值最终应该放置的位置，且 j 将数组有效分割。
我们将通过一个完整的 Java 代码示例来演示如何实现基于 Hoare 分区方案的快速排序。
这是快速排序的递归主函数。它接收一个整数数组、起始索引和结束索引（不包含）。
static void quickSort(int[] arg, int startIndex, int endIndex) {
// 基本情况：如果子数组的长度小于2，则无法再分区，直接返回
if (endIndex - startIndex < 2) {
return;
}
// 调用 getPivotIndex 方法进行分区，并获取枢轴最终的索引
int pivotIndex = getPivotIndex(arg, startIndex, endIndex);
// 对枢轴左侧的子数组进行递归排序
quickSort(arg, startIndex, pivotIndex);
// 对枢轴右侧的子数组进行递归排序
quickSort(arg, pivotIndex + 1, endIndex);
}这个方法实现了 Hoare 分区方案的核心逻辑。
private static int getPivotIndex(int[] arg, int startIndex, int endIndex) {
// 选择子数组的第一个元素作为枢轴值
int pivotVal = arg[startIndex];
// 初始化左指针和右指针
int i = startIndex;
int j = endIndex;
// 当左指针小于右指针时，继续进行分区
while (i < j) {
// 右指针从右向左移动，直到找到一个小于或等于枢轴的元素
// 注意：这里使用 --j 是因为 endIndex 是不包含的，所以 j 初始值是 endIndex，
// 第一次使用时会变为 endIndex - 1
while (i < j && (arg[--j] >= pivotVal));
// 如果左指针仍小于右指针，说明找到了一个需要移动到左侧的元素
if (i < j) {
arg[i] = arg[j]; // 将右侧找到的小于枢轴的元素移动到左指针当前位置
}
// 左指针从左向右移动，直到找到一个大于或等于枢轴的元素
// 注意：这里使用 ++i
while (i < j && (arg[++i] <= pivotVal));
// 如果左指针仍小于右指针，说明找到了一个需要移动到右侧的元素
if (i < j) {
arg[j] = arg[i]; // 将左侧找到的大于枢轴的元素移动到右指针当前位置
}
} // 循环结束时，i 和 j 相遇，此时 j 的位置就是枢轴值应该放置的位置
// 将枢轴值放到其最终的正确位置
arg[j] = pivotVal;
// 返回枢轴的最终索引
return j;
}public class QuickSortHoare {
public static void main(String[] args) {
int[] unsortedArray = {12, 3, 45, 23, 6, -4, -6, 10, 1, 8};
System.out.println("原始数组:");
for (int i : unsortedArray) {
System.out.print(i + " ");
}
System.out.println();
// 调用快速排序算法
quickSort(unsortedArray, 0, unsortedArray.length);
System.out.println("排序后的数组:");
// 打印排序后的数组
for (int i : unsortedArray) {
System.out.print(i + " ");
}
System.out.println();
}
/**
* 快速排序主函数，采用 Hoare 分区方案。
*
* @param arg 待排序的数组
* @param startIndex 子数组的起始索引（包含）
* @param endIndex 子数组的结束索引（不包含）
*/
static void quickSort(int[] arg, int startIndex, int endIndex) {
// 基本情况：如果子数组的长度小于2，则无法再分区，直接返回
if (endIndex - startIndex < 2) {
return;
}
// 调用 getPivotIndex 方法进行分区，并获取枢轴最终的索引
int pivotIndex = getPivotIndex(arg, startIndex, endIndex);
// 对枢轴左侧的子数组进行递归排序
quickSort(arg, startIndex, pivotIndex);
// 对枢轴右侧的子数组进行递归排序
quickSort(arg, pivotIndex + 1, endIndex);
}
/**
* 实现 Hoare 分区方案，将数组分为两部分并返回枢轴的最终索引。
*
* @param arg 待排序的数组
* @param startIndex 子数组的起始索引（包含）
* @param endIndex 子数组的结束索引（不包含）
* @return 枢轴的最终索引
*/
private static int getPivotIndex(int[] arg, int startIndex, int endIndex) {
// 选择子数组的第一个元素作为枢轴值
int pivotVal = arg[startIndex];
// 初始化左指针和右指针
int i = startIndex;
int j = endIndex;
// 当左指针小于右指针时，继续进行分区
while (i < j) {
// 右指针从右向左移动，直到找到一个小于或等于枢轴的元素
// 注意：这里使用 --j 是因为 endIndex 是不包含的，所以 j 初始值是 endIndex，
// 第一次使用时会变为 endIndex - 1
while (i < j && (arg[--j] >= pivotVal));
// 如果左指针仍小于右指针，说明找到了一个需要移动到左侧的元素
if (i < j) {
arg[i] = arg[j]; // 将右侧找到的小于枢轴的元素移动到左指针当前位置
}
// 左指针从左向右移动，直到找到一个大于或等于枢轴的元素
// 注意：这里使用 ++i
while (i < j && (arg[++i] <= pivotVal));
// 如果左指针仍小于右指针，说明找到了一个需要移动到右侧的元素
if (i < j) {
arg[j] = arg[i]; // 将左侧找到的大于枢轴的元素移动到右指针当前位置
}
} // 循环结束时，i 和 j 相遇，此时 j 的位置就是枢轴值应该放置的位置
// 将枢轴值放到其最终的正确位置
arg[j] = pivotVal;
// 返回枢轴的最终索引
return j;
}
}要运行上述代码，您可以将其保存为 QuickSortHoare.java 文件，然后使用 Java 编译器编译并运行：
javac QuickSortHoare.java java QuickSortHoare
预期输出：
原始数组: 12 3 45 23 6 -4 -6 10 1 8 排序后的数组: -6 -4 1 3 6 8 10 12 23 45
本教程详细介绍了使用 Hoare 分区方案实现快速排序算法的 Java 代码。通过理解分治思想、枢轴选择以及双指针移动和交换的分区逻辑，您可以有效地实现并应用快速排序。虽然快速排序在最坏情况下可能表现不佳，但通过优化枢轴选择策略，它在平均情况下的性能非常出色，是实际应用中最常用的排序算法之一。
以上就是实现 Hoare 分区方案的快速排序算法详解的详细内容，更多请关注php中文网其它相关文章！
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
广告Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
814
收藏
