引言：快速排序概述
快速排序（quicksort）是一种高效的、基于比较的排序算法，由c.a.r. hoare在1960年提出。它采用了“分而治之”（divide and conquer）的思想，其核心在于通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序的主要步骤包括：
- 选择基准值（Pivot Selection）：从数组中选择一个元素作为基准值。
- 分区（Partitioning）：重新排列数组，将所有小于基准值的元素移到基准值的左边，所有大于基准值的元素移到基准值的右边。在这个过程中，基准值会移动到其最终的排序位置。
- 递归排序（Recursive Sort）：递归地对基准值左右两边的子数组进行快速排序。
核心机制：就地分区（In-Place Partitioning）
分区操作是快速排序算法的灵魂。其目标是选择一个基准值，并通过一系列交换操作，将数组分为两部分：一部分包含所有小于基准值的元素，另一部分包含所有大于基准值的元素，并且将基准值放置到它在最终有序数组中的正确位置。本文将介绍一种常见的就地分区策略，该策略利用双指针技术实现。
分区函数详解：getPivotIndex
getPivotIndex 函数负责执行实际的分区操作，并返回基准值在排序后子数组中的最终索引。
- 基准值选择：在本实现中，我们简单地选择当前子数组的第一个元素 arg[startIndex] 作为基准值 (pivotVal)。虽然这种选择方式简单，但在某些情况下（如数组已部分有序或逆序），可能会导致性能下降。
-
双指针初始化：
- 左指针 i 初始化为 startIndex。
- 右指针 j 初始化为 endIndex（注意：endIndex 是不包含的边界）。
- 遍历与交换逻辑： while (i
-
右指针 j 移动：while (i = pivotVal));
- 右指针 j 从右向左移动（先自减），寻找第一个小于 pivotVal 的元素。
- 如果找到一个小于 pivotVal 的元素，并且 i
- 左指针 i 移动：while (i
- 左指针 i 从左向右移动（先自增），寻找第一个大于 pivotVal 的元素。
- 如果找到一个大于 pivotVal 的元素，并且 i
- 这个过程持续进行，直到 i 和 j 相遇或交叉。当它们相遇时，i 和 j 指向的将是基准值最终的正确位置。
- 基准值归位：循环结束后，i 和 j 相遇的位置就是基准值最终的正确位置。我们将最初选定的 pivotVal 放置于 arg[j]。
- 返回基准值索引：函数返回 j 作为基准值的最终索引。此时，arg[j] 左侧的所有元素都小于或等于 pivotVal，右侧的所有元素都大于或等于 pivotVal。
主排序函数：quickSort
quickSort 函数是快速排序的入口点，它负责处理递归调用。
- 递归基线条件：if (endIndex - startIndex
- 当子数组的长度小于2时（即子数组只包含0个或1个元素），表示子数组已经有序，无法再进行分区。这是递归的终止条件，直接返回。
-
分区调用：int pivotIndex = getPivotIndex(arg, startIndex, endIndex);
- 调用 getPivotIndex 函数，对当前子数组进行分区操作，并获取基准值在数组中的最终位置索引。
-
递归调用：
- quickSort(arg, startIndex, pivotIndex);：对基准值左侧的子数组（从 startIndex 到 pivotIndex，不包含 pivotIndex 处的基准值）进行递归排序。
- quickSort(arg, pivotIndex + 1, endIndex);：对基准值右侧的子数组（从 pivotIndex + 1 到 endIndex，不包含 endIndex）进行递归排序。
完整示例代码 (Java)
以下是上述快速排序算法的完整 Java 实现：
public class QuickSort_Impl {
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();
// 调用快速排序，对整个数组进行排序
// endIndex 使用数组长度，因为它是排他性的
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;
// 调用分区函数，找到基准值的最终位置，并完成一次分区。
int pivotIndex = getPivotIndex(arg, startIndex, endIndex);
// 递归排序基准值左侧的子数组。
// 范围从 startIndex 到 pivotIndex (不包含 pivotIndex)。
quickSort(arg, startIndex, pivotIndex);
// 递归排序基准值右侧的子数组。
// 范围从 pivotIndex + 1 到 endIndex (不包含 endIndex)。
quickSort(arg, pivotIndex + 1, endIndex);
}
/**
* 执行分区操作，并将基准值放置到其最终的排序位置。
* @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; // 右指针
// 当左指针 i 小于右指针 j 时，持续进行分区操作。
while (i < j) {
// 右指针 j 从右向左移动，寻找第一个小于基准值的元素。
// 注意：j 先自减，确保 j 指向有效元素。
while (i < j && (arg[--j] >= pivotVal));
// 如果找到，将该元素移动到 i 指向的位置。
if (i < j)
arg[i] = arg[j];
// 左指针 i 从左向右移动，寻找第一个大于基准值的元素。
// 注意：i 先自增，确保 i 指向有效元素。
while (i < j && (arg[++i] <= pivotVal));
// 如果找到，将该元素移动到 j 指向的位置。
if (i < j)
arg[j] = arg[i];
} // End Outer while
// 循环结束后，i 和 j 相遇，该位置就是基准值最终的排序位置。
// 将基准值放置到这个位置。
arg[j] = pivotVal;
// 返回基准值的最终索引。
return j;
}
}性能分析与注意事项
-
时间复杂度：
- 平均情况：O(n log n)。这是快速排序最常见的性能表现，非常高效。
- 最坏情况：O(n^2)。当基准值选择不当，导致每次分区都产生一个空子数组（例如，每次都选择最大或最小元素作为基准值，而数组已经有序或逆序），此时快速排序的性能会退化为类似于冒泡排序。
-
空间复杂度：
- 平均情况：O(log n)。这主要取决于递归调用的栈深度。
- 最坏情况：O(n)。在最坏情况下，递归深度可能达到 n。
-
基准值选择：
- 基准值的选择对快速排序的性能至关重要。本文示例中选择第一个元素作为基准值，这在某些特定输入下可能导致最坏情况。
-
优化策略包括：
- 随机选择：随机选择一个元素作为基准值，可以有效避免最坏情况的发生。
- 三数取中法：选择子数组的第一个、中间和最后一个元素，取它们的中位数作为基准值，这通常能更好地选择一个“中间”的基准值。
- 稳定性：快速排序通常不是稳定排序算法。这意味着具有相同值的元素的相对顺序在排序后可能发生改变。
-
与Lomuto/Hoare分区对比：
- 本文实现的这种分区策略是快速排序中常见且高效的一种，其核心是将基准值放置到最终位置。它与Lomuto分区法有异曲同工之处，都是在单次遍历中完成分区并确定基准位置。
- Hoare分区法是另一种经典的分区方案，它通常被认为在实践中比Lomuto分区法更高效，因为它交换的次数更少。Hoare分区法不保证基准值最终位于其精确的排序位置，但它保证基准值左侧的元素都小于或等于基准值，右侧的元素都大于或等于基准值。
总结
快速排序是一种功能强大且广泛应用的排序
