【java快速排序算法】快速排序（Quick Sort）是一种基于分治策略的高效排序算法，由Tony Hoare于1960年提出。它通过选择一个“基准”元素，将数组分为两个子数组：一个包含比基准小的元素，另一个包含比基准大的元素，然后递归地对这两个子数组进行排序。快速排序在平均情况下具有O(n log n)的时间复杂度，是实际应用中非常流行的排序算法之一。
一、快速排序的基本步骤
1. 选择基准：从数组中选择一个元素作为基准（pivot）。
2. 分区操作：将数组中的所有元素与基准比较，小于基准的放在左边，大于基准的放在右边。
3. 递归排序：对左右两个子数组重复上述过程，直到子数组长度为1或0时停止。
二、Java实现示例
```java
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);// 递归左半部分
quickSort(arr, pi + 1, high); // 递归右半部分
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];// 选取最后一个元素作为基准
int i = low - 1;// 较小元素的索引
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
// 交换元素
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 将基准放到正确的位置
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后的数组：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
三、性能对比表
| 特性 | 快速排序（Quick Sort） |
| 时间复杂度 | 平均 O(n log n)，最差 O(n²) |
| 空间复杂度 | O(log n)（递归栈） |
| 是否稳定 | 不稳定 |
| 是否原地排序 | 是 |
| 最坏情况 | 当输入已有序且选择第一个/最后一个元素作为基准 |
| 适用场景 | 大规模数据排序 |
| 优点 | 高效、实现简单 |
| 缺点 | 最坏情况下效率低 |
四、优化建议
- 基准选择：避免总是选择第一个或最后一个元素，可采用“三数取中法”或随机选择基准，以减少最坏情况发生的概率。
- 小数组切换排序算法：当子数组较小时，可以改用插入排序等更高效的算法。
- 尾递归优化：减少递归调用次数，提高程序运行效率。
五、总结
快速排序是一种高效、实用的排序算法，尤其适合大规模数据集。虽然其最坏时间复杂度较高，但通过合理的基准选择和优化策略，可以显著提升性能。在Java中实现快速排序相对简单，是学习排序算法的理想选择之一。
