【java快速排序算法】快速排序（Quick Sort）是一种高效的排序算法，基于分治法（Divide and Conquer）的策略。它通过选择一个“基准”元素，将数组分为两个子数组，一部分包含小于基准的元素，另一部分包含大于基准的元素，然后递归地对这两个子数组进行排序。
一、快速排序简介
| 项目 | 内容 |
| 算法类型 | 分治法 |
| 时间复杂度 | 平均 O(n log n)，最坏 O(n²) |
| 空间复杂度 | O(log n)（递归栈） |
| 稳定性 | 不稳定 |
| 是否原地排序 | 是 |
| 最佳应用场景 | 数据量大、需要高效排序的场景 |
二、快速排序原理
1. 选择基准（Pivot）：从数组中选择一个元素作为基准。
2. 分区（Partitioning）：将数组分成两部分，一部分比基准小，另一部分比基准大。
3. 递归排序：对左右两个子数组重复上述步骤。
三、Java实现示例
```java
public class QuickSort {
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
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[right]; // 选择最后一个元素为基准
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, right);
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};
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后的数组：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
四、快速排序优缺点
| 优点 | 缺点 |
| 高效，平均时间复杂度为 O(n log n) | 最坏情况下时间复杂度为 O(n²) |
| 原地排序，空间效率高 | 不稳定排序 |
| 实现简单，易于理解 | 对于小数据集性能不如插入排序 |
五、优化建议
- 基准选择：避免选择第一个或最后一个元素作为基准，可以随机选择或使用三数取中法。
- 小数组处理：当数组较小时，可以切换为插入排序以提高效率。
- 尾递归优化：减少递归调用次数，提升性能。
六、总结
快速排序是Java中常用的排序算法之一，具有较高的效率和良好的可读性。在实际应用中，合理选择基准和优化递归方式可以进一步提升其性能。对于大多数应用场景来说，快速排序是一个值得推荐的排序方法。
