java如何快速排序
快速排序实现方法
快速排序（QuickSort）是一种高效的分治算法，平均时间复杂度为 O(n log n)。以下是Java实现的核心步骤和代码示例。
核心逻辑
-
选择基准值（Pivot）
从数组中选择一个元素作为基准值（通常选择第一个、最后一个或中间元素）。 -
分区（Partitioning）
将数组分为两部分：小于基准值的元素移到左侧，大于基准值的元素移到右侧。分区完成后，基准值处于正确的位置。 -
递归排序
对左右子数组递归执行上述步骤，直到子数组长度为1或0。
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; // i指向小于基准值的区域边界
for (int j = low; j < high; j++) {
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;
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr)); // 输出排序后的数组
}
}关键点说明
- 基准值选择：示例中选择数组末尾元素作为基准值，但可优化为随机选择或三数取中法以避免最坏情况（如数组已有序时时间复杂度退化为 O(n²)）。
- 分区优化：Lomuto分区方案（如上代码）简单但效率较低；Hoare分区方案（双指针法）通常性能更好。
- 稳定性：快速排序是不稳定的排序算法，相同元素的相对位置可能改变。
时间复杂度分析
- 最佳/平均情况：O(n log n)。
- 最坏情况（如数组已有序）：O(n²)，可通过随机化基准值避免。
