《Java 实现快速排序：原理剖析与代码详解》
目录
一、引言
二、快速排序原理
1. 选择基准值
2. 划分操作
3. 递归排序
三、代码分析
1. 代码整体结构
2. main方法
3. sort方法（快速排序核心逻辑）
四、测试结果
一、引言
排序算法在数据处理和计算机编程领域中占据着举足轻重的地位，它们能够将无序的数据按照特定的规则整理成有序的序列，方便后续的分析与操作。快速排序作为一种高效且应用广泛的排序算法，以其独特的分治思想和相对优秀的时间复杂度表现备受关注。在这篇博客中，我们将深入解析一段用 Java 实现快速排序的代码，帮助大家透彻理解快速排序的原理以及代码的具体实现细节。
二、快速排序原理
快速排序基于分治策略，其核心思想可以概括为以下几个步骤：
1. 选择基准值
首先从待排序的数组中选取一个元素作为基准值（pivot）。这个基准值的选取方式有多种，常见的是选取数组的第一个元素、最后一个元素或者中间元素等。在我们给出的代码中，选取的是数组的第一个元素作为基准值。
2. 划分操作
将数组划分为两部分，使得左边部分的所有元素都小于等于基准值，右边部分的所有元素都大于等于基准值。这一步是通过两个游标（指针）从数组的两端开始向中间移动来实现的。具体操作如下：
- 一个游标从数组的末尾开始，向前移动，直到找到一个小于基准值的元素。
- 另一个游标从数组的开头开始，向后移动，直到找到一个大于基准值的元素。
- 当这两个游标找到符合条件的元素后，将它们所指向的元素进行交换。
- 不断重复上述过程，直到两个游标相遇。
3. 递归排序
在完成一次划分操作后，基准值就处于它在排序后应该所处的大致位置（即左边的元素都比它小，右边的元素都比它大）。然后，对划分后的左右两部分子数组分别递归地应用快速排序算法，直到整个数组都被排序完成。
三、代码分析
1. 代码整体结构
以下是我们要详细分析的 Java 快速排序代码：
package 排序;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5, 7, 4, 2, 0, 3, 1, 6};
sort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
//定义变量保存基准数
int base = arr[left];
//定义一个i游标和j游标
int i = left;
int j = right;
while (i!= j) {
//j游标从后往前移动，找比基准数小的
while (arr[j] >= base && i < j) {
j--;
}
//i游从前往后，找比基准数大的
while (arr[i] <= base && i < j) {
i++;
}
//交换
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//i和j相遇,基准数和相遇位置进行交换
arr[left] = arr[i];
arr[i] = base;
//排序左边
sort(arr, left, i - 1);
//排序右边
sort(arr, i + 1, right);
}
}
2. main方法
在 main 方法中，首先定义了一个整数数组 arr，并初始化其值为 {5, 7, 4, 2, 0, 3, 1, 6}。这就是我们要进行排序的原始数组。
int[] arr = {5, 7, 4, 2, 0, 3, 1, 6};
然后调用了 sort 方法，并将数组 arr 以及数组的起始索引 0 和结束索引 arr.length - 1 作为参数传递给它，目的是对整个数组进行排序操作。
sort(arr, 0, arr.length - 1);
最后，在排序完成后，使用 Arrays.toString 方法将排序后的数组以字符串的形式输出到控制台，以便直观地查看排序的结果。
System.out.println(Arrays.toString(arr));
3. sort方法（快速排序核心逻辑）
sort 方法实现了快速排序的核心逻辑，下面我们来详细剖析其内部的操作。
- 递归终止条件：
当left大于等于right时，意味着当前子数组的长度为 0 或 1，已经是排序好的状态，所以直接返回，不再进行排序操作。
if (left >= 23;
return;
}
- 选择基准值：
选取数组的第一个元素作为基准值，并将其保存在变量base中。
int base = arr[left];
-
划分操作（双游标移动与交换）：
定义了两个游标i和j，分别初始化为数组的起始索引left和结束索引right。然后通过两个嵌套的while循环来实现划分操作。-
外层
while循环：
条件是i!= j，确保两个游标没有相遇，只要它们没有相遇，就继续在数组中寻找可以交换的元素。 -
内层第一个
while循环：
从数组的末尾（由j指向）开始，向前移动游标j，只要arr[j] >= base（即当前元素大于等于基准值）且i < j（确保游标还没有相遇），就继续让j往前移动，直到找到一个小于基准值的元素为止。 -
内层第二个
while样：
从数组的开头（由i指向）开始，向后移动游标i，只要arr[i] <= base（即当前元素小于等于基准值）且i < j（确保游标还没有相遇），就继续让i往后移动，直到找到一个大于基准值的元素为止。 -
元素交换：
当两个游标i和j分别找到符合条件的元素后（即arr[j] < base且arr[i] > base），通过临时变量temp来交换它们所指向的元素，使得数组的左边部分逐渐出现小于等于基准值的元素，右边部分逐渐出现大于等于基准值的元素。
-
while (arr[j] >= base && i < j) {
j--;
}
while (arr[i] <= base && i < j) {
i++;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
- 基准值归位：
当两个游标i和j相遇时，将基准值base（最初保存在arr[left]）与相遇位置的元素（此时arr[i]）进行交换，这样基准值就处于它在排序后应该所处的大致位置，即左边的元素都比它小，右边的元素都比它大。
arr[left] = arr[i];
arr[i] = base;
- 递归排序左右子数组：
在完成一次划分操作后，对划分后的左右两部分子数组分别递归地应用快速排序算法。对左边子数组，调用sort方法，传入起始索引left和结束索引i - 1；对右边子数组，调用sort方法，传入起始索引i + 1和结束索引right。通过不断递归，直到整个数组都被排序完成。
//排序左边
sort(arr, left, i - 1);
//排序右边
sort(arr, i + 1, right);
四、测试结果
当我们运行上述代码时，对于给定的初始数组 {5, 7, 4, 2, 0, 3, 1, 6}，经过快速排序后，控制台会输出排序后的数组，其结果应该是 {0, 1, 2, 3, 4, 5, 6, 7}。