推广百度百科_济南专业网站建设哪家便宜_怎么建立企业网站_广告宣传语

原理

快速排序（Quick Sort）是一种高效的分治排序算法
通过一次划分（Partition）将待排序数组分成两个子数组，然后递归地对子数组排序，最终完成整个数组的排序。

算法步骤

选择基准（Pivot）：
从数组中选择一个元素作为基准（通常选第一个、最后一个或随机元素）。
划分（Partition）：
将数组重新排列，使得：

- 所有小于基准的元素移到基准的左侧。
- 所有大于基准的元素移到基准的右侧。
- 基准位于最终正确的位置（即排序后的位置）。

递归排序：
对基准左侧和右侧的子数组分别递归调用快速排序。

代码实现

import java.util.Arrays;public class QuickSort {// 快速排序的入口方法public static void quickSort(int[] arr) {if (arr == null || arr.length == 0) {return;}quickSort(arr, 0, arr.length - 1);}// 递归排序的核心方法private static void quickSort(int[] arr, int low, int high) {if (low < high) {// 找到划分点 pivotIndexint 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 是小于基准区域的右边界for (int j = low; j < high; j++) {if (arr[j] <= pivot) {i++;swap(arr, i, j); // 将小于基准的元素交换到左侧}}// 将基准放到正确位置（i+1）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;}// 测试代码public static void main(String[] args) {int[] arr = {10, 7, 8, 9, 1, 5};System.out.println("排序前: " + Arrays.toString(arr));quickSort(arr);System.out.println("排序后: " + Arrays.toString(arr));}
}

随机优化

int randomPivotIndex = low + (int)(Math.random() * (high - low + 1));
swap(arr, randomPivotIndex, high); // 将随机选中的基准交换到末尾
pivot = arr[high];

快速排特点分析

1. 时间复杂度（Time Complexity）

快速排序的时间复杂度取决于 划分（Partition）的平衡性。

情况	时间复杂度	说明
最优情况	(O(n \log n))	每次划分都能将数组均匀分成两部分（类似二分）。
平均情况	(O(n \log n))	随机数据下，划分较均衡，递归深度为 (\log n)。
最坏情况	(O(n^2))	每次划分都极不平衡（如数组已有序，且基准选择不当）。

最坏情况举例

如果数组已经有序（升序或降序），并且 总是选择第一个或最后一个元素作为基准，那么每次划分只能减少一个元素，导致递归深度为 (n)，时间复杂度退化为 (O(n^2))。

如何避免最坏情况？

随机选择基准（Randomized Quick Sort）。
三数取中法（Median-of-Three）：选择 arr[low]、arr[mid]、arr[high] 的中位数作为基准。

2. 空间复杂度（Space Complexity）

快速排序是 原地排序（In-place），但递归调用会占用栈空间。

情况	空间复杂度	说明
最优/平均情况	(O(\log n))	递归深度为 (\log n)，栈空间占用较小。
最坏情况	(O(n))	递归深度为 (n)（如数组已有序）。

优化空间复杂度的方法：

尾递归优化（Tail Recursion Optimization）：减少递归栈深度。
迭代实现（非递归）：用栈模拟递归过程，避免栈溢出。

3. 稳定性（Stability）

快速排序是不稳定的排序算法。

- 在交换元素时，可能改变相同值的相对顺序。

为什么不稳定？

- 在 partition 过程中，i 和 j 的交换可能导致相同元素的相对位置发生变化。

举例说明

假设有一个数组 [3a, 2, 3b, 1]（3a 和 3b 是值相同的 3，但 a 和 b 用于区分它们的原始顺序）：

选择基准：pivot = 1（最后一个元素）。
partition 过程：

- i = -1，j 从 0 开始遍历：

- - arr[0] = 3a > 1，不交换，i 不移动。
  - arr[1] = 2 > 1，不交换，i 不移动。
  - arr[2] = 3b > 1，不交换，i 不移动。

- 最后，i + 1 = 0，交换 arr[0] 和 pivot（arr[3]）：

- - 交换后数组：[1, 2, 3b, 3a]（3a 和 3b 的相对顺序已经改变！）。

结果：

排序前：[3a, 2, 3b, 1]
排序后：[1, 2, 3b, 3a]（3a 和 3b 的顺序颠倒了 → 不稳定）

4. 优化策略

（1）随机化基准（Randomized Quick Sort）

避免最坏情况，提高平均性能。
实现方式：

int randomPivotIndex = low + (int)(Math.random() * (high - low + 1));
swap(arr, randomPivotIndex, high); // 随机选择一个基准，并交换到末尾
pivot = arr[high];

（2）三数取中法（Median-of-Three）

选择 arr[low]、arr[mid]、arr[high] 的中位数作为基准，减少最坏情况的概率。
实现方式：

int mid = low + (high - low) / 2;
// 确保 arr[low] <= arr[mid] <= arr[high]
if (arr[low] > arr[mid]) swap(arr, low, mid);
if (arr[mid] > arr[high]) swap(arr, mid, high);
if (arr[low] > arr[mid]) swap(arr, low, mid);
pivot = arr[mid]; // 选择中位数作为基准

（3）小数组改用插入排序

当子数组较小时（如 size < 10），插入排序比快速排序更快（减少递归开销）。
实现方式：

if (high - low + 1 < 10) {insertionSort(arr, low, high);return;
}

（4）双轴快排（Dual-Pivot Quick Sort）

Java 的 Arrays.sort() 对基本类型使用 双轴快排，比经典快排更快。
它选择 两个基准（Pivot），将数组分成 三部分：

- < pivot1、>= pivot1 && <= pivot2、> pivot2。

优化了经典快排的划分方式，减少比较次数。

5. 快速排序 vs 归并排序 vs 堆排序

算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性	适用场景
快速排序	(O(n \log n))	(O(n^2))	(O(\log n))	不稳定	通用排序，实际最快
归并排序	(O(n \log n))	(O(n \log n))	(O(n))	稳定	外部排序（大数据）
堆排序	(O(n \log n))	(O(n \log n))	(O(1))	不稳定	内存受限场景

为什么 Java 的 Arrays.sort() 对基本类型用双轴快排，对对象用归并排序？

基本类型（int, double 等）：不需要稳定性，双轴快排更快。
对象类型（String, Object 等）：需要稳定性，归并排序更合适。

6. 总结

特性	快速排序
时间复杂度（平均）	(O(n \log n))
时间复杂度（最坏）	(O(n^2))（可优化）
空间复杂度	(O(\log n))（递归栈）
稳定性	不稳定
优化方式	随机化基准、三数取中、小数组插入排序、双轴快排
适用场景	通用内部排序，实际应用中最快

适用场景：

适用于 大规模数据排序，在大多数情况下比归并排序和堆排序更快。
不适合稳定性要求高的场景（如数据库索引排序）。

优化后的快速排序（如随机化 + 三数取中 + 小数组优化）在工程实践中几乎不会出现最坏情况，是最高效的排序算法之一。