你好！作为一名开发者，我们经常需要在处理数据时做出选择：是追求极致的速度，还是保证绝对的稳定？在排序算法的世界里，快速排序 无疑是那个追求极致速度的“王者”。就像它的名字一样，它非常快。
在这篇文章中，我们将通过 Java 的视角，深入探讨快速排序的核心机制。你不仅会学到它如何工作，还会理解为什么它在大多数实际应用中（例如 Java 标准库的 Arrays.sort）被优先选择。我们将一起编写代码，分析它的性能瓶颈，并探讨如何优化它。准备好和我一起探索这个经典的分治算法了吗？
什么是快速排序？
与[归并排序]一样，快速排序也是一种分治算法。它的核心思想非常直观：
- 挑选基准：从数组中选出一个元素作为“基准”。
- 分区操作：重新排列数组，使得所有比基准小的元素放在基准前面，所有比基准大的元素放在后面。这个操作完成后，基准就处于了它在最终排序数组中的正确位置。
- 递归排序：递归地对基准左侧的子数组和右侧的子数组进行排序。
我们可以通过这个简单的逻辑将一个大问题分解为两个小问题，这正是分治法的精髓。
基准的选取策略
快速排序有许多不同的版本，关键的区别在于如何选取基准。这不仅影响代码的实现，更直接影响算法在最坏情况下的性能。以下是几种常见的策略：
- 总是选取第一个元素：实现简单，但如果数组本身已经有序或接近有序，性能会急剧下降（退化到 O(N²)）。
- 总是选取最后一个元素：最常用的教学演示方式（下面的实现采用了这种方式）。优点是代码逻辑清晰，便于理解索引移动的过程。
- 随机选取一个元素：通过随机性来规避最坏情况，是一种稳健的策略。
- 选取中位数：通常取“首、中、尾”三个元素的中位数作为基准。这是很多工业级库（如 C++ std::sort）的优化手段，能有效减少最坏情况发生的概率。
快速排序的核心：分区算法
让我们把目光聚焦在快速排序的灵魂——INLINECODEc9b8a958 函数上。这个函数的目标是：给定一个数组和一个数组元素 INLINECODEcb3a9326 作为基准，将 INLINECODEfd5d4446 放置在排序后数组中的正确位置，并将所有小于（或等于）INLINECODE1aeac2f4 的元素放在 INLINECODE67510b9c 之前，将所有大于 INLINECODE1820a908 的元素放在 x 之后。所有这些操作都必须在线性时间内完成。
让我们来看看标准的 Java 实现。
基础实现：Lomuto 分区方案
这种方案以最后一个元素作为基准，逻辑非常易于理解。我们维护一个指针 i，它始终指向“小于基准的区域”的末尾。
// Java Program for implementation of QuickSort
class QuickSort {
/*
* 这个函数选取最后一个元素作为基准，
* 将基准元素放置在排序数组中的正确位置，
* 并将所有小于基准的元素移到其左侧，
* 所有大于基准的元素移到其右侧。
*/
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选取最后一个元素作为基准
int i = (low - 1); // i 是“小于基准区域”的索引指针，初始化为 low-1
for (int j = low; j < high; j++) {
// 如果当前元素小于或等于基准
if (arr[j] 待排序数组
* low --> 起始索引
* high --> 结束索引
*/
void sort(int arr[], int low, int high) {
if (low < high) {
/* pi 是分区索引，arr[pi] 现在位于正确位置 */
int pi = partition(arr, low, high);
// 递归地排序分区前后的元素
sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}
}
// 打印数组的辅助函数
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// 主驱动程序
public static void main(String args[]) {
int arr[] = { 10, 7, 8, 9, 1, 5 };
int n = arr.length;
QuickSort ob = new QuickSort();
ob.sort(arr, 0, n - 1);
System.out.println("Sorted array");
printArray(arr);
}
}
输出
Sorted array
1 5 7 8 9 10
进阶实现：Hoare 分区方案
你可能会问，有没有更高效一点的分区方式？当然有。Hoare 分区方案使用两个指针从数组的两端向中间扫描，直到它们找到需要交换的元素。虽然它的逻辑稍微复杂一点，但在实际运行中通常比 Lomuto 方案更快，因为它减少了交换的次数。
class QuickSortHoare {
/* Hoare 分区法的实现
这里我们选取第一个元素作为基准 */
int partition(int arr[], int low, int high) {
int pivot = arr[low];
int i = low - 1;
int j = high + 1;
while (true) {
// 从左向右找第一个大于等于 pivot 的元素
do {
i++;
} while (arr[i] pivot);
// 如果指针相遇或交叉，返回 j
if (i >= j)
return j;
// 交换这两个不满足条件的元素
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
/* 使用 Hoare 分区的快速排序主函数 */
void sort(int arr[], int low, int high) {
if (low < high) {
// pi 是分区索引，注意这里不包括 pi 本身在下一轮递归中
// Hoare 分区返回的点并不一定是 pivot 的最终位置，
// 但它确保了左侧都小，右侧都大。
int pi = partition(arr, low, high);
sort(arr, low, pi);
sort(arr, pi + 1, high);
}
}
// ... printArray 和 main 方法与上述类似 ...
}
代码是如何工作的？
让我们以第一个代码示例（Lomuto 方案）为基础，逐步分解执行过程。假设数组为 INLINECODEc231cf45，基准选为 INLINECODEf59315d8。
- 初始化：INLINECODE2d415549 从 INLINECODE7f7f7415 开始。
j开始遍历。 - j=0 (10)：INLINECODE5a7c24b2。INLINECODE69bb51b6 变为 INLINECODE5599ece8。交换 INLINECODE0115f85c 和
arr[0]（没变）。 - j=1 (80)：
80 > 40。不做操作。 - j=2 (30)：INLINECODE92076b11。INLINECODE0b7563d9 变为 INLINECODE30c2c95b。交换 INLINECODE620df76e (80) 和 INLINECODE7a6313bb (30)。数组变为 INLINECODE4759da2c。
- j=3 (90)：
90 > 40。不做操作。 - 最后交换：循环结束。INLINECODE51fdef25 是 INLINECODE818e4c3b。交换 INLINECODE7e98c86d (即 80) 和基准 INLINECODE479769a9 (40)。数组变为
{10, 30, 40, 90, 80}。
现在，INLINECODE4175ec78 已经在正确的位置了（索引 2）。左边是 INLINECODEd96b3c90，右边是 {90, 80}。我们递归重复这个过程。
深入分析：时间复杂度与空间复杂度
理解算法的优缺点至关重要。
时间复杂度分析
- 最优情况：O(N log N)。这发生在每次分区都能将数组大致均匀地分成两部分时。
- 平均情况：O(N log N)。经过数学证明，这是快速排序在随机数据下的表现。
- 最坏情况：O(N²)。这发生在每次分区都将数组分成极度不平衡的两部分（例如一边是 0 个元素，另一边是 N-1 个元素）。常见场景包括：数组已经有序且我们总是选择第一个或最后一个元素作为基准。
辅助空间
- 平均/最优情况：O(log N)。这是递归调用栈所需的栈空间。
- 最坏情况：O(N)。当树退化成链表时，递归深度达到 N。
实战应用与最佳实践
虽然归并排序也是 O(N log N)，但快速排序通常在实践中更快，因为它的内部循环非常紧凑，对现代 CPU 的缓存非常友好。但在实际工程中，我们很少直接使用上面的“裸”代码。我们需要做以下优化：
优化 1：小数组使用插入排序
对于非常小的数组（例如长度小于 10 或 20），递归的开销相对于问题规模来说太大了。插入排序 在这种小规模数据上表现优异。我们可以修改代码：
void sort(int arr[], int low, int high) {
// 优化：当子数组很小时，使用插入排序
if (high - low < 10) { // 阈值可调整
insertionSort(arr, low, high);
return;
}
if (low < high) {
int pi = partition(arr, low, high);
sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}
}
// 简单的插入排序实现
void insertionSort(int arr[], int low, int high) {
for (int i = low + 1; i = low && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
优化 2：三数取中法
为了防止有序数组导致的最坏情况，我们可以不再简单地选取 INLINECODE7692d9a8，而是选取 INLINECODE607edfd8、INLINECODEc3365c0d 和 INLINECODEba26ae5d 中的中位数作为基准。这大大降低了遇到 O(N²) 的概率。
优化 3：三向切分快速排序
如果数组中有大量重复元素怎么办？标准的快速排序会反复递归处理这些相等的元素，效率低下。我们可以使用三向切分（Dijkstra 的 3-way partitioning），将数组分为：小于基准、等于基准、大于基准三部分。这样等于基准的部分就可以直接跳过。
void sort3Way(int arr[], int low, int high) {
if (high <= low) return;
int lt = low, gt = high;
int pivot = arr[low]; // 选取第一个元素为基准
int i = low;
while (i <= gt) {
if (arr[i] pivot) {
swap(arr, i, gt--);
} else {
i++;
}
}
// 现在 arr[low..lt-1] pivot
sort3Way(arr, low, lt - 1);
sort3Way(arr, gt + 1, high);
}
void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
常见错误与解决方案
在编写或面试中，你可能会遇到这些坑：
- 索引越界：这是最常见的错误。在 Lomuto 方案中，务必注意 INLINECODE0265aa54 循环中的 INLINECODEcfe7dbdd（不包括 high，因为 high 是基准）。如果不小心写成
j <= high，就会导致越界。 - 死循环：在 Hoare 分区方案中，如果递归边界处理不当（比如直接把 INLINECODE2027da1e 包含进下一轮递归且没有移动指针），可能会导致无限递归。记住 Hoare 方法的递归范围通常是 INLINECODE3a4f2fad 和
(pi+1, high)。 - 最坏情况忽略：很多人只记得快速排序是 O(N log N)，却忘了有序输入会导致 O(N²)。在实际开发中，一定要考虑随机化基准或使用“三数取中”。
性能优化建议总结
- 随机化基准：在最开始时，将
arr[high]与一个随机位置的元素交换，然后再开始分区。这能有效防御恶意数据导致的 O(N²) 攻击。 - 尾递归优化：对于较长的子数组先递归，较短的子数组使用循环（模拟尾递归），可以限制递归栈的最大深度，防止栈溢出。
- 处理重复元素：使用三向切分。
关键要点与后续步骤
通过这篇文章，我们不仅实现了快速排序，还深入探讨了它的多种分区策略、时间复杂度分析以及针对重复元素和有序数组的优化方案。
核心要点：
- 平均性能：快速排序是目前基于比较的排序算法中平均性能最好的之一。
- 不稳定：快速排序是不稳定的排序算法（即相同元素的相对位置可能会改变）。
- 原地排序：它不需要像归并排序那样额外的 O(N) 空间来合并数组。
后续步骤建议：
我强烈建议你自己动手实现一遍这些代码。尝试打印出每一次分区后的数组状态，观察指针是如何移动的。此外，你可以尝试写一个性能测试，对比“插入排序”、“标准快速排序”和“三向切分快速排序”在处理大量重复数据时的耗时差异。这将帮助你更深刻地理解算法在真实场景下的表现。
希望这篇文章对你有所帮助！如果你有任何疑问，欢迎随时在评论区留言讨论。