在 Java 中，快速排序（Quick Sort）是一种常用的排序算法，它的核心思想是通过分治的方式将数组分成两部分，一部分小于基准元素，一部分大于基准元素，然后递归地对这两部分进行排序。
下面我会介绍三种不同的实现方式，并提供每种方式的详细步骤流程和示例代码。这些示例代码将基于纯 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++;
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 = {5, 2, 9, 3, 5, 6};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
随机化快速排序在选择基准元素时，通过随机选择一个元素来降低最坏情况的概率。
步骤与经典快速排序类似，只是在选择基准元素时有所不同。
public class RandomizedQuickSort {
public static void randomizedQuickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = randomizedPartition(arr, low, high);
randomizedQuickSort(arr, low, pivotIndex - 1);
randomizedQuickSort(arr, pivotIndex + 1, high);
}
}
private static int randomizedPartition(int[] arr, int low, int high) {
int randomIndex = low + new Random().nextInt(high - low + 1);
swap(arr, randomIndex, high);
return partition(arr, low, high);
}
// ... 其他方法与方式一相同 ...
}
Java 标准库提供了 Arrays 类中的 sort 方法，可以用于进行快速排序。
import java.util.Arrays;
public class ArraysSort {
public static void main(String[] args) {
int[] arr = {5, 2, 9, 3, 5, 6};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
无需手动实现快速排序，直接调用 Java 标准库的 Arrays.sort 方法即可完成排序。
这些实现方式不依赖于任何第三方库，如果你仍然想知道相关库的依赖信息，可以使用以下坐标：
Maven 依赖（添加到 pom.xml ）：
<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-lang3</artifactId>
<version>3.12.0</version>
</dependency>
Gradle 依赖（添加到 build.gradle ）：
implementation 'org.apache.commons:commons-lang3:3.12.0'
然后，你可以使用 ArrayUtils 类中的 swap 方法来交换数组中的元素。不过，在示例代码中，我已经提供了一个自定义的 swap 方法来执行此操作。
