Java 快速排序(QuickSort)原理及实现代码

快速排序（QuickSort）是一种高效的排序算法，它采用分而治之的策略来对一个数组进行排序。其核心思想是选取一个“基准”元素，通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

下面是快速排序的一个简单Java实现：

public class QuickSort {

    /**
     * 快速排序方法
     * @param arr 待排序数组
     * @param low 排序范围的起始索引
     * @param high 排序范围的结束索引
     */
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // partitionIndex是分区操作后基准值的最终位置
            int partitionIndex = partition(arr, low, high);

            // 递归地对基准值左边的子数组进行快速排序
            quickSort(arr, low, partitionIndex - 1);

            // 递归地对基准值右边的子数组进行快速排序
            quickSort(arr, partitionIndex + 1, high);
        }
    }

    /**
     * 分区操作
     * @param arr 待排序数组
     * @param low 排序范围的起始索引
     * @param high 排序范围的结束索引
     * @return 分区后基准值的索引
     */
    private static int partition(int[] arr, int low, int high) {
        // 选择最右边的元素作为基准值
        int pivot = arr[high];

        // i用于标记小于基准值的最后一个元素的索引
        int i = low - 1;

        for (int j = low; j < high; j++) {
            // 如果当前元素小于或等于基准值
            if (arr[j] <= pivot) {
                i++;

                // 交换arr[i]和arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 将基准值放到中间位置
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    // 示例用法
    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

在这个实现中，`quickSort` 方法是快速排序的递归实现，而 `partition` 方法则负责进行分区操作，选择最右边的元素作为基准值，通过遍历数组将小于基准值的元素放到基准值的左边，大于基准值的元素放到基准值的右边，并返回基准值最终的位置。最后，在 `main` 方法中提供了一个示例数组，并调用 `quickSort` 方法对其进行排序。