核心思路
快速排序是Java中Arrays.sort()的实现原理，采用分治策略，通过选择基准元素，将数组分为两个子数组，使得左边元素 ≤ 基准元素 ≤ 右边元素，然后递归排序子数组。
举个简单的例子，图书管理员需要按照书本厚度对一箱书进行排序，使用快速排序就是先选择一本书作为中间基准，把厚的书放在它右边，薄的书放在它左边。（这里左右两边内部是无序的）
处理完后再对它左边的书分别快速排序（即选出新的基准元素，厚的放右边，薄的放左边），同理右边也是一样，最后就得到完整的序列。
复杂度
| 情况 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 最好情况 | O(n logn) | O(logn) |
| 最坏情况 | O(n²) | O(n) |
| 平均情况 | O(n logn) | O(logn) |
优缺点
优点：
- 平均情况下最快的比较排序算法
- 原地排序（不需要额外内存）
- 高度可优化
缺点：
- 最坏情况时间复杂度较高
- 不稳定排序
- 递归实现需要栈空间
适用场景：
- 大规模数据排序
- 需要高效率的通用排序
- 内存受限环境
代码实现（Java）
public class QuickSort {public static void main(String[] args) {int[] arr = {5, 3, 8, 4, 2};quickSort(arr, 0, arr.length - 1);System.out.println(Arrays.toString(arr)); }public static void quickSort(int[] arr, int low, int high) {if (low < high) {//选出基准元素int pivotIndex = partition(arr, low, high);//排序左半部quickSort(arr, low, pivotIndex - 1); //排序右半部quickSort(arr, pivotIndex + 1, high); }}/*** 分区（这里以最后一个元素为基准）*/private static int partition(int[] arr, int low, int high) {//基准元素int pivot = arr[high]; //小元素区间的左边界int i = low - 1; //i+1实际上就是最后基准元素要被移到的位置for (int j = low; j < high; j++) {//把小于基准的元素不断向左靠拢（比基准大的元素也被动地向右边移动），//最后[low,i]的元素都比基准小，那么i+1的位置自然就留给基准元素了if (arr[j] <= pivot) {i++;swap(arr, i, j);}}//移动基准元素swap(arr, i + 1, high); return i + 1;}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}排序过程
初始数组：[5, 3, 8, 4, 2]
第1次分区（pivot=2）
移动元素：5>2，3>2，8>2，4>2 → 无交换
最终交换基准 → [2, 3, 8, 4, 5]
返回位置0递归左半部（空数组）和右半部[3,8,4,5]
第2次分区（pivot=5）
排序数组：[3,8,4,5]
移动元素：3<5，8>5，4<5 → 交换8和4
最终数组：[3,4,5,8]
返回位置2递归处理左右子数组
左半部[3,4] → 最终排序[3,4]
右半部[8] → 保持原样最终结果
[2, 3, 4, 5, 8]
