Java 快速排序算法
最后修改时间：2025 年 4 月 16 日
排序算法简介
算法是解决问题或执行计算的逐步过程。排序算法按特定顺序排列元素，通常是数字或按字典顺序排列。高效排序对于优化其他算法至关重要。
常见的排序算法包括冒泡排序、选择排序、插入排序、归并排序、堆排序和快速排序。每种算法都有不同的时间和空间复杂度特征，使其适用于不同的场景。
快速排序概述
快速排序是一种分而治之的算法，它通过选择一个“枢轴”元素并围绕它对数组进行分区来工作。小于枢轴的元素移到它的左边，较大的元素移到它的右边。此过程为子数组重复进行。
快速排序的平均时间复杂度为 O(n log n)，使其成为最快的排序算法之一。但是，当枢轴选择不佳时，其最坏情况性能为 O(n²)。
基本快速排序实现
这是按升序对整数进行快速排序的基本实现。该算法递归地对数组进行分区，直到所有元素都排序完毕。
QuickSort.java
package com.zetcode;
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++;
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[] data = { 10, 7, 8, 9, 1, 5 };
System.out.println("Unsorted array:");
printArray(data);
quickSort(data, 0, data.length - 1);
System.out.println("Sorted array in ascending order:");
printArray(data);
}
private static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
此实现显示了核心快速排序算法。partition 方法选择最后一个元素作为枢轴，并将其放置在其正确的位置。所有较小的元素都位于枢轴的左侧，较大的元素都位于枢轴的右侧。
快速排序降序
修改 partition 方法中的比较允许以降序排序。只需要将比较运算符从 < 更改为 >。
QuickSortDescending.java
package com.zetcode;
public class QuickSortDescending {
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) { // Changed from < to >
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[] data = { 10, 7, 8, 9, 1, 5 };
System.out.println("Unsorted array:");
printArray(data);
quickSort(data, 0, data.length - 1);
System.out.println("Sorted array in descending order:");
printArray(data);
}
private static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
降序排序唯一需要的更改是 partition 方法中的比较运算符。这表明了快速排序通过简单修改可以具有多大的灵活性。
字符串的快速排序
快速排序还可以对文本数据进行排序。该实现类似，但使用 String 比较方法而不是数值比较。
StringQuickSort.java
package com.zetcode;
public class StringQuickSort {
private static void quickSort(String[] 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(String[] arr, int low, int high) {
String pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j].compareTo(pivot) < 0) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
private static void swap(String[] arr, int i, int j) {
String temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
String[] names = { "John", "Alice", "Bob", "Eve", "David" };
System.out.println("Unsorted array:");
printArray(names);
quickSort(names, 0, names.length - 1);
System.out.println("Sorted array in ascending order:");
printArray(names);
}
private static void printArray(String[] arr) {
for (String str : arr) {
System.out.print(str + " ");
}
System.out.println();
}
}
此版本使用 compareTo 方法按字典顺序对字符串进行排序。通过更改比较，可以修改相同的方法以降序排序。
通用快速排序实现
使用 Java 泛型，我们可以创建一个适用于任何 Comparable 类型的快速排序实现。这使得代码更具可重用性和类型安全性。
GenericQuickSort.java
package com.zetcode;
public class GenericQuickSort<T extends Comparable<T>> {
private void quickSort(T[] 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 int partition(T[] arr, int low, int high) {
T pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j].compareTo(pivot) < 0) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
private void swap(T[] arr, int i, int j) {
T temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
// Sorting integers
Integer[] numbers = { 10, 7, 8, 9, 1, 5 };
GenericQuickSort<Integer> intSorter = new GenericQuickSort<>();
intSorter.quickSort(numbers, 0, numbers.length - 1);
System.out.println("Sorted integers:");
printArray(numbers);
// Sorting strings
String[] names = { "John", "Alice", "Bob", "Eve", "David" };
GenericQuickSort<String> stringSorter = new GenericQuickSort<>();
stringSorter.quickSort(names, 0, names.length - 1);
System.out.println("Sorted strings:");
printArray(names);
}
private static <T> void printArray(T[] arr) {
for (T element : arr) {
System.out.print(element + " ");
}
System.out.println();
}
}
这个 Java 示例演示了 QuickSort 算法的通用实现，允许它对任何实现 Comparable 接口的类型的数组进行排序。该程序包括递归执行排序、使用枢轴元素对数组进行分区以及交换元素的方法。 main 方法通过对整数和字符串进行排序来展示其多功能性。然后打印排序后的数组的结果，突出显示通用 QuickSort 实现的可重用性和适应性。
快速排序与插入排序基准测试
对于大型数据集，快速排序通常优于插入排序。插入排序对于小型或接近排序的数据更有效。让我们比较一下它们的性能。
SortBenchmark.java
package com.zetcode;
import java.util.Random;
public class SortBenchmark {
private 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++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
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[] sizes = { 100, 1000, 10000, 50000 };
Random random = new Random();
for (int size : sizes) {
int[] arr1 = new int[size];
int[] arr2 = new int[size];
for (int i = 0; i < size; i++) {
int num = random.nextInt(size * 10);
arr1[i] = num;
arr2[i] = num;
}
// Quick Sort benchmark
long start = System.nanoTime();
quickSort(arr1, 0, arr1.length - 1);
long quickTime = System.nanoTime() - start;
// Insertion Sort benchmark
start = System.nanoTime();
insertionSort(arr2);
long insertionTime = System.nanoTime() - start;
System.out.printf("Size: %d | Quick Sort: %d ns | Insertion Sort: %d ns%n",
size, quickTime, insertionTime);
}
}
}
此基准测试比较了不同数组大小的快速排序和插入排序。随着数据集的增长，快速排序表现出更好的性能，而插入排序对于非常小的数组可能更快。
优化快速排序
一些优化可以提高快速排序的性能。这些包括
- 三数取中枢轴选择以避免最坏情况
- 用于小子数组的插入排序（通常在大小 < 10 时）
- 尾递归消除以减少堆栈空间
- 用于具有许多重复项的数组的三向分区
这是一个结合了这些技术的优化实现。
OptimizedQuickSort.java
package com.zetcode;
public class OptimizedQuickSort {
private static final int INSERTION_THRESHOLD = 10;
private static void quickSort(int[] arr, int low, int high) {
while (low < high) {
if (high - low < INSERTION_THRESHOLD) {
insertionSort(arr, low, high);
break;
} else {
int pi = partition(arr, low, high);
// Tail recursion optimization
if (pi - low < high - pi) {
quickSort(arr, low, pi - 1);
low = pi + 1;
} else {
quickSort(arr, pi + 1, high);
high = pi - 1;
}
}
}
}
private static int partition(int[] arr, int low, int high) {
// Median-of-three pivot selection
int mid = low + (high - low) / 2;
if (arr[high] < arr[low]) swap(arr, low, high);
if (arr[mid] < arr[low]) swap(arr, low, mid);
if (arr[high] < arr[mid]) swap(arr, mid, high);
int pivot = arr[mid];
swap(arr, mid, high - 1);
int i = low;
int j = high - 1;
while (true) {
while (arr[++i] < pivot);
while (arr[--j] > pivot);
if (i >= j) break;
swap(arr, i, j);
}
swap(arr, i, high - 1);
return i;
}
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--;
}
arr[j + 1] = key;
}
}
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[] data = { 10, 7, 8, 9, 1, 5, 3, 12, 4, 11 };
System.out.println("Unsorted array:");
printArray(data);
quickSort(data, 0, data.length - 1);
System.out.println("Sorted array in ascending order:");
printArray(data);
}
private static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
优化的 QuickSort 算法是传统 QuickSort 的高级变体，旨在提高性能并更有效地处理边缘情况。 它使用混合方法，切换到插入排序以处理较小的子数组（由定义的阈值确定），以利用其较低的开销。 这确保了小型数据集的更快排序，同时保持了 QuickSort 对较大数组的分而治之的特性。
一个重要的特性是三数取中枢轴选择，它通过减少不平衡拆分的可能性来改进分区。 通过选择第一个、中间和最后一个元素的中值作为枢轴，该算法避免了不良枢轴选择的陷阱，从而导致更均匀分布的分区。 这降低了遇到 QuickSort 最坏情况性能的可能性。
另一个关键优化是尾递归减少。 该算法不是盲目地使用递归调用，而是优先使用递归对较小的子数组进行排序，并以迭代方式对较大的子数组进行排序。 这最大限度地减少了堆栈的使用，防止了大型数据集的堆栈溢出，并确保了更好的可扩展性。 结合起来，这些增强功能使该算法在不同的数据大小和场景中既可靠又高效。
何时使用快速排序
由于快速排序的平均情况性能为 O(n log n)，因此它是大型数据集的理想选择。 它在实践中被广泛使用，包括在 Java 的 Arrays.sort 中，用于原始类型。 但是，对于非常小的数组或接近排序的数据，像插入排序这样的简单算法可能更快。 上面显示的优化使快速排序对于各种场景都具有鲁棒性。
在实际应用中，对于大多数排序任务，应首选 Java 的 Arrays.sort，因为它经过高度优化并能有效地处理边缘情况。
来源
在本文中，我们介绍了 Java 中的快速排序算法，包括基本和优化实现，升序和降序排序不同数据类型，泛型实现以及与插入排序的性能比较。
作者
列出所有Java教程。