【java快速排序算法】快速排序（Quick Sort）是一种高效的排序算法，采用分治策略来对一个数组进行排序。它通过选择一个“基准”元素，将数组分为两个子数组：一个包含比基准小的元素，另一个包含比基准大的元素，然后递归地对这两个子数组进行排序。
一、快速排序原理总结
快速排序的基本思想是：
1. 选择基准（pivot）：从数组中选择一个元素作为基准。
2. 分区（partitioning）：将所有小于基准的元素移到左边，大于基准的元素移到右边。
3. 递归排序：对左右两个子数组重复上述过程，直到子数组长度为0或1。
该算法的时间复杂度平均为 O(n log n)，最坏情况下为 O(n²)，但通过合理选择基准可以避免最坏情况。
二、Java实现快速排序
以下是一个简单的 Java 实现示例：
```java
public class QuickSort {
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; // 比基准小的元素的索引
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 + " ");
}
}
}
```
三、快速排序特点对比表
| 特性 | 快速排序 |
| 稳定性 | 不稳定 |
| 时间复杂度 | 平均 O(n log n)，最坏 O(n²) |
| 空间复杂度 | O(log n)（递归栈） |
| 是否需要额外空间 | 否（原地排序） |
| 适用场景 | 大数据集，尤其适合随机数据 |
| 基准选择影响 | 是（如选中间值或随机值可优化性能） |
| 实现难度 | 中等 |
四、总结
快速排序是一种高效且广泛使用的排序算法，尤其在实际应用中表现优异。虽然其最坏时间复杂度较高，但通过合理的基准选择和优化策略，可以有效避免这一问题。在 Java 中实现快速排序相对简单，适用于多种排序需求。对于初学者来说，理解其分治思想和分区逻辑是掌握该算法的关键。