JavaJDK中的快速排序实现及其过程解析

快速排序是一种基于分治策略的高效排序算法。它的基本思想是通过一个划分操作将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再递归地在这两部分数据中继续进行同样的操作，直到整个数据变成有序。

假设我们有一个数组 [52, 39, 67, 95, 70, 8, 25, 52] 需要排序。首先，选择一个基准值（pivot），通常可以选择数组的第一个元素。然后，将数组中小于基准值的元素放到基准值的左边，大于基准值的元素放到右边。例如，选择 70 作为基准值，经过一次划分后，数组可能变为 [8, 25, 39, 52, 52, 67, 70, 95]。

快速排序的关键在于如何高效地完成划分操作。一种常见的方法是从数组的两端开始，分别向中间移动，直到找到一个需要交换的位置。具体步骤如下：

• 从右向左扫描，找到第一个小于基准值的元素。
• 从左向右扫描，找到第一个大于基准值的元素。
• 交换这两个元素的位置。
• 重复上述步骤，直到两个指针相遇。

划分完成后，基准值已经位于正确的位置，接下来递归地对基准值左右两边的子数组进行相同的操作，直到整个数组排序完成。

快速排序的时间复杂度取决于输入数据的初始状态。在最好的情况下，每次划分都能将数组均匀分成两半，此时的时间复杂度为 O(n log n)。而在最坏的情况下，每次划分只能将数组分成一个元素和剩余部分，此时的时间复杂度为 O(n^2)。为了提高性能，可以采用一些优化策略，如随机选择基准值、使用三数取中法等。

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

package sort;

public class QuickSort {
    public void quickSort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private void sort(int[] arr, int low, int high) {
        if (low >= high) return;
        int pivotIndex = partition(arr, low, high);
        sort(arr, low, pivotIndex - 1);
        sort(arr, pivotIndex + 1, high);
    }

    private int partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        int i = low + 1, j = high;
        while (true) {
            while (i <= j && arr[i]             while (i <= j && arr[j] > pivot) j--;
            if (i >= j) break;
            swap(arr, i, j);
        }
        swap(arr, low, j);
        return j;
    }

    private 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 = {52, 39, 67, 95, 70, 8, 25, 52};
        new QuickSort().quickSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}