Java 快速排序算法实现及详解

以下是 Java 中快速排序算法的实现示例：

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = { 5, 6, 9, 2, 8, 3, 7, 1, 4 };
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotPosition = partition(arr, low, high);
            quickSort(arr, low, pivotPosition - 1);
            quickSort(arr, pivotPosition + 1, high);
        }
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        int i = low + 1;
        int j = high;

        while (i <= j) {
            if (arr[i] <= pivot) {
                i++;
            } else if (arr[j] > pivot) {
                j--;
            } else {
                swap(arr, i, j);
                i++;
                j--;
            }
        }

        swap(arr, low, j);
        return j;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

在上面的代码中，我们首先定义了一个 main 方法和一个 quickSort 方法。main 方法仅仅是为了测试我们的快速排序算法。quickSort 方法是我们实现快速排序的地方。

快速排序的思想是选择一个枢纽元素，将小于该元素的元素放在左侧，大于该元素的元素放在右侧。我们选择第一个元素作为枢纽元素，然后使用 i 和 j 指针来遍历数组。i 指针从左侧开始，j 指针从右侧开始。当 arr[i] 小于或等于枢纽元素时，i 将继续向右移动。当 arr[j] > 枢纽元素时，j 将继续向左移动。当 arr[i] > 枢纽元素，arr[j] <= 枢纽元素时，我们将交换 arr[i] 和 arr[j]。最后，我们将枢纽元素放在正确的位置，并返回该位置。

我们还定义了一个 swap 方法，用于交换数组中两个元素的位置。

快速排序算法的步骤：

1. 选择一个枢纽元素。
2. 将数组划分为两个子数组：小于枢纽元素的元素放在左侧，大于枢纽元素的元素放在右侧。
3. 递归地对两个子数组进行快速排序。

快速排序算法的时间复杂度：

平均情况下，快速排序算法的时间复杂度为 O(n log n)，最坏情况下为 O(n^2)。

快速排序算法的空间复杂度：

快速排序算法的空间复杂度为 O(log n)。