Java 中的快速排序算法
简介
快速排序（Quicksort）是一种高效的排序算法，由英国计算机科学家托尼·霍尔（Tony Hoare）在1960年开发。它采用了分治法（Divide and Conquer）的思想，在平均情况下具有 O(n log n) 的时间复杂度，最坏情况下为 O(n^2)。在 Java 中，快速排序算法可以很方便地实现，并且在许多实际应用场景中表现出色。本文将详细介绍 Java 中快速排序的基础概念、使用方法、常见实践以及最佳实践。
目录
- 基础概念
- 使用方法
- 代码示例
- 常见实践
- 随机化枢轴
- 小数组优化
- 最佳实践
- 优化分区策略
- 并行化快速排序
- 小结
- 参考资料
基础概念
快速排序的基本思想是通过选择一个枢轴（pivot）元素，将数组分为两部分：小于枢轴的元素放在左边，大于枢轴的元素放在右边。然后对这两个子数组分别进行快速排序，直到整个数组有序。具体步骤如下： 1. 选择枢轴：从数组中选择一个元素作为枢轴。常见的选择方法有选择第一个元素、最后一个元素或随机选择一个元素。 2. 分区操作：通过比较和交换元素，将数组分为两部分，使得左边的元素都小于等于枢轴，右边的元素都大于等于枢轴。 3. 递归排序：对左右两个子数组分别递归地进行上述步骤，直到子数组的大小为 1 或 0，此时数组已经有序。
使用方法
代码示例
public class QuickSort {
// 分区函数
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++;
// 交换 arr[i] 和 arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 交换 arr[i+1] 和 arr[high]（枢轴）
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
// 快速排序主函数
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// pi 是分区索引，arr[pi] 现在在正确的位置
int pi = partition(arr, low, high);
// 分别对分区前后的子数组进行排序
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
System.out.println("排序前的数组:");
for (int num : arr) {
System.out.print(num + " ");
}
quickSort(arr, 0, arr.length - 1);
System.out.println("\n排序后的数组:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
代码说明
partition方法负责将数组分为两部分，返回枢轴的最终位置。quickSort方法递归地对左右两个子数组进行排序。- 在
main方法中，我们创建了一个示例数组，并调用quickSort方法对其进行排序。
常见实践
随机化枢轴
为了避免在最坏情况下的 O(n^2) 时间复杂度，可以随机选择枢轴元素。这样可以减少输入数据对算法性能的影响。
private static int partition(int[] arr, int low, int high) {
// 随机选择枢轴
int randomIndex = low + (int) (Math.random() * (high - low + 1));
int pivot = arr[randomIndex];
// 将随机选择的枢轴与最后一个元素交换
int temp = arr[randomIndex];
arr[randomIndex] = arr[high];
arr[high] = temp;
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
// 交换 arr[i] 和 arr[j]
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 交换 arr[i+1] 和 arr[high]（枢轴）
temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
小数组优化
对于小数组，快速排序的递归调用开销可能会超过其排序效率。此时可以使用插入排序等简单排序算法对小数组进行排序。
private static void insertionSort(int[] arr, int low, int high) {
for (int i = low + 1; i <= high; i++) {
int key = arr[i];
int j = i - 1;
while (j >= low && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
if (high - low + 1 <= 16) {
insertionSort(arr, low, high);
return;
}
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
最佳实践
优化分区策略
可以使用三向切分（Dutch National Flag Algorithm）来优化分区过程，将数组分为三部分：小于枢轴、等于枢轴和大于枢轴的元素。这样可以避免对等于枢轴的元素进行不必要的排序。
private static void threeWayPartition(int[] arr, int low, int high) {
int pivot = arr[high];
int lt = low;
int gt = high;
int i = low;
while (i <= gt) {
if (arr[i] < pivot) {
int temp = arr[lt];
arr[lt] = arr[i];
arr[i] = temp;
lt++;
i++;
} else if (arr[i] > pivot) {
int temp = arr[gt];
arr[gt] = arr[i];
arr[i] = temp;
gt--;
} else {
i++;
}
}
}
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
threeWayPartition(arr, low, high);
quickSort(arr, low, low + high - 1);
quickSort(arr, low + high + 1, high);
}
}
并行化快速排序
在多核处理器上，可以通过并行化快速排序来提高性能。Java 的 Fork/Join 框架可以方便地实现并行快速排序。
import java.util.concurrent.RecursiveAction;
public class ParallelQuickSort extends RecursiveAction {
private static final int THRESHOLD = 16;
private final int[] array;
private final int low;
private final int high;
public ParallelQuickSort(int[] array, int low, int high) {
this.array = array;
this.low = low;
this.high = high;
}
@Override
protected void compute() {
if (high - low <= THRESHOLD) {
insertionSort(array, low, high);
} else {
int pi = partition(array, low, high);
ParallelQuickSort leftTask = new ParallelQuickSort(array, low, pi - 1);
ParallelQuickSort rightTask = new ParallelQuickSort(array, pi + 1, high);
leftTask.fork();
rightTask.compute();
leftTask.join();
}
}
private 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;
}
private void insertionSort(int[] arr, int low, int high) {
for (int i = low + 1; i <= high; i++) {
int key = arr[i];
int j = i - 1;
while (j >= low && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
System.out.println("排序前的数组:");
for (int num : arr) {
System.out.print(num + " ");
}
ParallelQuickSort sorter = new ParallelQuickSort(arr, 0, arr.length - 1);
sorter.compute();
System.out.println("\n排序后的数组:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
小结
快速排序是一种高效的排序算法，在 Java 中实现快速排序需要理解其基本概念和分治思想。通过随机化枢轴、小数组优化、优化分区策略和并行化等方法，可以进一步提高快速排序的性能。在实际应用中，应根据具体需求选择合适的优化策略，以达到最佳的排序效果。
参考资料
- 《算法导论》（Introduction to Algorithms），Thomas H. Cormen 等著
- 维基百科 - 快速排序
- Oracle Java 教程