快速排序（quicksort）是一种高效的、基于比较的排序算法，由c.a.r. hoare在1960年提出。它采用了“分而治之”（divide and conquer）的思想，其核心在于通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序的主要步骤包括：
分区操作是快速排序算法的灵魂。其目标是选择一个基准值，并通过一系列交换操作，将数组分为两部分：一部分包含所有小于基准值的元素，另一部分包含所有大于基准值的元素，并且将基准值放置到它在最终有序数组中的正确位置。本文将介绍一种常见的就地分区策略，该策略利用双指针技术实现。
getPivotIndex 函数负责执行实际的分区操作，并返回基准值在排序后子数组中的最终索引。
quickSort 函数是快速排序的入口点，它负责处理递归调用。
以下是上述快速排序算法的完整 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;
}
}快速排序是一种功能强大且广泛应用的排序
以上就是深入理解快速排序：一种高效的就地分区实现的详细内容，更多请关注php中文网其它相关文章！
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
广告Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
793
收藏
