核心结论，快速排序是基于分治思想的经典排序算法，Java 实现核心逻辑是挑选基准元素 pivot，把数组划分成小于基准、大于基准两部分，再递归对左右子区间继续排序，平均时间复杂度 O (n log n)，属于原地排序，是 Java 面试高频算法题，相比冒泡排序效率更高，缺点是最坏情况时间复杂度退化到 O (n²)，递归深度过大还可能触发栈溢出。
算法核心原理
分治三步走
1 分解，选定基准值，执行分区 partition 操作，基准左侧全部小于等于基准，基准右侧全部大于基准
2 递归，对基准左边子数组递归快速排序
3 递归，对基准右边子数组递归快速排序
终止条件，区间左边界大于等于右边界，代表子区间只有 0 或者 1 个元素，天然有序，停止递归
关键概念说明
基准 pivot，一般选择首元素、尾元素或者随机元素，随机选基准可以降低有序数组下算法退化概率
分区 partition，双指针交换，把元素按照基准大小重新摆放，返回基准最终下标
原地排序，不需要额外开辟完整数组，只使用少量临时变量交换元素，空间复杂度平均 O (log n)，主要是递归栈占用
Java 完整代码实现
public class QuickSort {
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
int i = left;
int j = right;
while (i < j) {
while (i < j && arr[j] >= pivot) {
j--;
}
while (i < j && arr[i] <= pivot) {
i++;
}
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 基准归位
arr[left] = arr[i];
arr[i] = pivot;
return i;
}
public static void main(String[] args) {
int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
quickSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
复杂度与特性对照表
| 项目 | 数值 |
|---|---|
| 平均时间复杂度 | O(n log n) |
| 最坏时间复杂度 | O (n²)，数组已经有序且固定选首元素基准 |
| 最好时间复杂度 | O(n log n) |
| 平均空间复杂度 | O (log n) 递归栈 |
| 排序稳定性 | 不稳定排序，相等元素相对顺序可能改变 |
| 排序类型 | 原地排序 |
优化方案深度说明
1 随机基准优化，每次分区随机挑选 pivot，避免原数组有序导致算法退化
2 三数取中，取左中右三个元素中间值作为基准，进一步均衡分区
3 小区间切换插入排序，当子数组长度很小的时候，递归开销大于插入排序，切换插入排序提升性能
4 尾递归优化，减少递归栈深度，降低 StackOverflowError 风险
执行流程演示
原始数组 [6,1,2,7,9,3,4,5,10,8]
第一轮选择基准 6，分区之后基准 6 落到中间位置，左边全部小于 6，右边全部大于 6
之后递归排序左区间 [1,2,3,4,5] 和右区间 [7,9,10,8]
不断重复分区递归，直到所有子区间长度为 1，数组整体升序完成
和 Java 内置排序关联
JDK 里面 Arrays.sort 对基本类型数组底层使用的是双轴快速排序 DualPivotQuicksort，是传统快速排序的改进版本，优化了分区逻辑，性能比普通单轴快排更好。
【常见问题】
问题 1 java 快速排序算法是稳定排序吗
回答 1 java 快速排序算法属于不稳定排序，分区交换的时候相等元素原有相对顺序有可能发生改变，这是 java 快速排序算法重要特性
问题 2 java 快速排序算法最坏情况为什么变成 O (n²)
回答 1 java 快速排序算法如果数组本身有序，每次选择第一个元素作为基准，分区极度不均衡，每次只分出一个元素，递归层数变成 n，时间复杂度退化为 O (n²)
问题 3 java 快速排序算法递归报错 StackOverflowError 是什么原因
回答 1 java 快速排序算法递归深度过大就会触发栈溢出，数组长度很大或者分区不均衡的时候容易出现，java 快速排序算法可以通过优化基准选择缓解该问题
问题 4 java 快速排序算法平均时间复杂度是多少
回答 1 java 快速排序算法平均时间复杂度是 O (n log n)，是 java 快速排序算法最核心考点，面试经常和归并排序对比考察
【免责申明】
本文内容为 java 快速排序算法原理与代码科普讲解，不同教材分区写法存在差异，算法优化方案可以根据学习需求调整，本文不构成考试唯一标准答案。