【基础3】快速排序

核心思路

快速排序是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]