快速排序概述
快速排序（QuickSort）是一种广泛使用的、基于比较的排序算法，以其平均时间复杂度为O(n log n)而闻名。其核心思想是“分而治之”：选择一个“基准元素”（pivot），通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比基准元素小，另一部分记录的关键字均比基准元素大，然后分别对这两部分记录继续进行排序，直到整个序列有序。
快速排序的性能很大程度上取决于基准元素的选择和分区（Partition）策略的实现。常见的有Lomuto分区方案和Hoare分区方案。本文将重点介绍一种Hoare分区法的实现，它通过双指针从两端向中间移动来完成分区操作。
Hoare分区法详解
Hoare分区法通常被认为比Lomuto分区法更高效，尤其是在处理重复元素较多的数组时。它的主要思想是，选择数组的第一个元素作为基准值，然后使用两个指针（i 和 j）分别从数组的两端向中间移动，寻找需要交换的元素。
1. getPivotIndex 方法：实现分区逻辑
getPivotIndex 方法是整个快速排序算法的核心，它负责将当前子数组根据基准值划分为两部分，并返回基准值最终的索引。
private static int getPivotIndex(int[] arg, int startIndex, int endIndex) {
int pivotVal = arg[startIndex]; // 选择子数组的第一个元素作为基准值
int i = startIndex;
int j = endIndex; // 注意：endIndex在此处是独占的，即子数组范围是 [startIndex, endIndex-1]
while (i < j) {
// 从右向左遍历，寻找第一个小于基准值的元素
// 遇到大于等于基准值的元素时，j指针继续向左移动
while (i < j && (arg[--j] >= pivotVal));
// 如果找到小于基准值的元素（且i < j），将其移动到i指针当前位置
if (i < j)
arg[i] = arg[j];
// 从左向右遍历，寻找第一个大于基准值的元素
// 遇到小于等于基准值的元素时，i指针继续向右移动
while (i < j && (arg[++i] <= pivotVal));
// 如果找到大于基准值的元素（且i < j），将其移动到j指针当前位置
if (i < j)
arg[j] = arg[i];
} // 当i >= j时，循环结束，此时i和j指向同一个位置，即基准值的最终位置
// 将基准值放到其最终的排序位置
arg[j] = pivotVal;
// 返回基准值的索引
return j;
}工作原理细分：
- 基准值选择： 示例代码选择子数组的第一个元素 arg[startIndex] 作为基准值 pivotVal。
-
指针初始化：
- i 指针从 startIndex 开始（子数组的左端）。
- j 指针从 endIndex 开始（子数组的右端，但由于 endIndex 是独占的，j 实际上指向子数组最后一个元素的下一位）。
-
双向遍历与交换：
-
右侧遍历 (j 指针)： while (i = pivotVal))
- --j：j 指针首先向左移动一位，指向当前子数组的最后一个元素。
- arg[j] >= pivotVal：如果 j 指向的元素大于或等于基准值，说明它在正确的一侧，j 继续向左移动。
- 当 j 停止时，arg[j] 要么小于 pivotVal，要么 i 和 j 相遇。如果 arg[j]
- arg[i] = arg[j]：将这个小于基准值的元素移动到 i 指针当前的位置（i 此时指向一个大于基准值的元素或待填充位置）。
- 左侧遍历 (i 指针)： while (i
- ++i：i 指针首先向右移动一位。
- arg[i]
- 当 i 停止时，arg[i] 要么大于 pivotVal，要么 i 和 j 相遇。如果 arg[i] > pivotVal 且 i
- arg[j] = arg[i]：将这个大于基准值的元素移动到 j 指针当前的位置（j 此时指向一个小于基准值的元素或待填充位置）。
-
右侧遍历 (j 指针)： while (i = pivotVal))
- 基准值归位： 当 i 和 j 指针相遇或交叉时，循环结束。此时 j 指针（或 i 指针，因为它们指向同一个位置）所指向的位置就是 pivotVal 最终的正确位置。将最初的 pivotVal 放入 arg[j]。
- 返回基准值索引： 返回 j 作为基准值的新索引。
2. quickSort 方法：递归排序子数组
quickSort 方法负责处理整个排序过程，它通过递归调用自身来对分区后的子数组进行排序。
static void quickSort(int[] arg, int startIndex, int endIndex) {
// 基本情况：如果子数组的长度小于2，则无需分区，直接返回
// 数组长度为0或1时，认为已经有序
if (endIndex - startIndex < 2)
return;
// 调用getPivotIndex方法进行分区，获取基准值的最终索引
int pivotIndex = getPivotIndex(arg, startIndex, endIndex);
// 递归排序基准值左侧的子数组
quickSort(arg, startIndex, pivotIndex);
// 递归排序基准值右侧的子数组
quickSort(arg, pivotIndex + 1, endIndex);
}工作原理：
- 基本情况： if (endIndex - startIndex
- 分区： 调用 getPivotIndex 方法，将当前子数组 arg[startIndex...endIndex-1] 分区。pivotIndex 是基准值在排序后的最终位置。
-
递归调用：
- quickSort(arg, startIndex, pivotIndex)：对基准值左侧的子数组进行递归排序。注意，这里的 pivotIndex 是独占的，所以左侧子数组的范围是 [startIndex, pivotIndex-1]。
- quickSort(arg, pivotIndex + 1, endIndex)：对基准值右侧的子数组进行递归排序。右侧子数组的范围是 [pivotIndex + 1, endIndex-1]。
完整代码示例
public class QuickSort_Impl {
public static void main(String[] args) {
int[] unsortedArray = {12, 3, 45, 23, 6, -4, -6, 10, 1, 8};
// 调用快速排序方法
// 注意：endIndex通常是数组长度，表示排序范围是 [0, unsortedArray.length-1]
quickSort(unsortedArray, 0, unsortedArray.length);
// 打印排序后的数组
System.out.println("排序后的数组：");
for (int i : unsortedArray)
System.out.print(i + " ");
System.out.println();
}
/**
* 快速排序主方法
*
* @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; // 注意：endIndex在此处是独占的，即子数组范围是 [startIndex, endIndex-1]
// 当i < j时，双指针继续移动和交换
while (i < j) {
// 从右向左遍历，寻找第一个小于基准值的元素
// j指针先自减，再进行比较
while (i < j && (arg[--j] >= pivotVal));
// 如果找到小于基准值的元素，将其移动到i指针当前位置
if (i < j)
arg[i] = arg[j];
// 从左向右遍历，寻找第一个大于基准值的元素
// i指针先自增，再进行比较
while (i < j && (arg[++i] <= pivotVal));
// 如果找到大于基准值的元素，将其移动到j指针当前位置
if (i < j)
arg[j] = arg[i];
} // 循环结束时，i和j指向同一个位置，即基准值的最终位置
// 将基准值放到其最终的排序位置
arg[j] = pivotVal;
// 返回基准值的索引
return j;
}
}注意事项与总结
- 基准值选择： 本示例选择子数组的第一个元素作为基准值。虽然简单，但在某些极端情况下（如已排序或逆序数组）可能导致性能下降到O(n^2)。更优的策略包括随机选择基准值或“三数取中”法。
- endIndex 的含义： 在本实现中，endIndex 是一个独占索引，表示子数组的范围是 [startIndex, endIndex-1]。理解这一点对于正确编写递归边界和指针移动逻辑至关重要。
- 性能： Hoare分区法在平均情况下表现优秀，时间复杂度为O(n log n)。虽然在最坏情况下（如基准值选择不当）会退化到O(n^2)，但通过优化基准值选择可以有效避免。
- 空间复杂度： 快速排序的空间复杂度主要取决于递归栈的深度，平均情况下为O(log n)，最坏情况下为O(n)。
- 稳定性： 快速排序通常不是一个稳定排序算法，即相等元素的相对顺序在排序后可能会改变。
通过本文的详细解析和代码示例，读者应该能够清晰地理解并实现基于Hoare分区法的快速排序算法。掌握这种高效的排序技术对于任何Java开发者来说都是一项宝贵的技能。
