在 Java 中，快速排序（Quick Sort）是一种高效的排序算法，其平均时间复杂度为 O(n log n)。以下将介绍两种实现方式：递归版本和迭代版本。
public class QuickSortRecursive {
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[low];
int left = low + 1;
int right = high;
while (left <= right) {
while (left <= right && arr[left] <= pivot) {
left++;
}
while (left <= right && arr[right] >= pivot) {
right--;
}
if (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
arr[low] = arr[right];
arr[right] = pivot;
return right;
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 1, 5, 6};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
import java.util.Arrays;
import java.util.Stack;
public class QuickSortIterative {
public static void quickSort(int[] arr) {
Stack<Integer> stack = new Stack<>();
stack.push(0);
stack.push(arr.length - 1);
while (!stack.isEmpty()) {
int high = stack.pop();
int low = stack.pop();
int pivotIndex = partition(arr, low, high);
if (pivotIndex - 1 > low) {
stack.push(low);
stack.push(pivotIndex - 1);
}
if (pivotIndex + 1 < high) {
stack.push(pivotIndex + 1);
stack.push(high);
}
}
}
private static int partition(int[] arr, int low, int high) {
// ... 同上 ...
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 1, 5, 6};
quickSort(arr);
System.out.println(Arrays.toString(arr));
}
}
这两种版本的快速排序均使用基准元素来进行分区，将小于基准的元素放在左边，大于基准的元素放在右边，然后对左右子数组递归或迭代地应用快速排序。在实际应用中，你可以根据需要选择合适的实现方式。至于 Maven 和 Gradle 的依赖坐标，这里不涉及外部库的使用，所以不需要相关依赖。
