快速排序概述
快速排序（quicksort）是一种高效的、基于比较的排序算法，其核心思想是“分而治之”（divide and conquer）。它通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，最终使整个数据序列有序。
快速排序的关键在于“分区”操作。常见的分区方案有两种：Lomuto 分区和 Hoare 分区。本教程将重点介绍 Hoare 分区方案的实现。
Hoare 分区方案详解
Hoare 分区方案是快速排序的原始设计，它通常比 Lomuto 分区更高效，因为它执行的交换次数更少。Hoare 分区的基本思想是：
- 选择枢轴（Pivot）：从待排序的数组中选择一个元素作为枢轴。在本实现中，我们选择子数组的第一个元素作为枢轴。
- 双指针移动：使用两个指针 i 和 j。i 从子数组的起始位置开始向右移动，j 从子数组的结束位置开始向左移动。
-
比较与交换：
- 指针 j 从右向左移动，直到找到一个小于或等于枢轴的元素。
- 指针 i 从左向右移动，直到找到一个大于或等于枢轴的元素。
- 如果 i
- 枢轴归位：当 i >= j 时，循环结束。此时，指针 j 所在的元素就是枢轴最终的正确位置。所有 j 左边的元素都小于或等于枢轴，所有 j 右边的元素都大于或等于枢轴。
这种分区方式将数组分为两部分，枢轴本身可能不在最终的 j 位置，但 j 位置是枢轴值最终应该放置的位置，且 j 将数组有效分割。
Java 实现
我们将通过一个完整的 Java 代码示例来演示如何实现基于 Hoare 分区方案的快速排序。
1. quickSort 方法
这是快速排序的递归主函数。它接收一个整数数组、起始索引和结束索引（不包含）。
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);
}2. getPivotIndex 方法（分区逻辑）
这个方法实现了 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;
}3. 完整代码示例
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
注意事项与性能分析
-
枢轴选择：本实现选择子数组的第一个元素作为枢轴。虽然简单，但如果输入数组已经部分有序或完全有序，这种选择可能导致最坏情况，即每次分区都将数组分为一个空子数组和一个 n-1 大小的子数组，使得时间复杂度退化到 O(n²)。更优的枢轴选择策略包括：
- 随机选择枢轴：从子数组中随机选择一个元素作为枢轴。
- 三数取中法：选择子数组的第一个、中间和最后一个元素，取它们的中位数作为枢轴。
-
时间复杂度：
- 平均情况：O(n log n)。在大多数情况下，快速排序表现优秀。
- 最坏情况：O(n²)。当枢轴选择不当，导致每次分区都产生极度不平衡的子数组时发生（例如，选择最大或最小元素作为枢轴）。
- 空间复杂度：O(log n)（平均情况），主要由递归调用栈的深度决定。最坏情况下，递归深度可能达到 O(n)。
- 稳定性：快速排序是一种不稳定的排序算法，因为它在分区过程中可能会交换相等元素的相对顺序。
-
Hoare 分区与 Lomuto 分区：
- Hoare 分区：通常执行更少的交换操作，因此在实际应用中可能更快。它将数组分为两个子数组，枢轴最终的位置在 j 处，但 arg[j] 不一定是原始的枢轴值。
- Lomuto 分区：保证枢轴最终会放置在其排序后的最终位置，并且其左侧所有元素都小于它，右侧所有元素都大于它。Lomuto 分区通常需要更多的交换操作。
总结
本教程详细介绍了使用 Hoare 分区方案实现快速排序算法的 Java 代码。通过理解分治思想、枢轴选择以及双指针移动和交换的分区逻辑，您可以有效地实现并应用快速排序。虽然快速排序在最坏情况下可能表现不佳，但通过优化枢轴选择策略，它在平均情况下的性能非常出色，是实际应用中最常用的排序算法之一。
