Java 中的快速排序代码解析

简介

快速排序（Quick Sort）是一种高效的排序算法，由计算机科学家托尼·霍尔（Tony Hoare）在1960年提出。它采用了分治（Divide and Conquer）的思想，在平均情况下具有 $O(n log n)$ 的时间复杂度，在最坏情况下时间复杂度为 $O(n^2)$。本文将深入探讨如何在 Java 中实现快速排序，包括基础概念、使用方法、常见实践以及最佳实践。

快速排序基础概念

快速排序的核心思想是通过选择一个基准值（pivot），将数组分为两部分：小于基准值的元素放在左边，大于基准值的元素放在右边。然后递归地对左右两部分进行同样的操作，直到整个数组有序。

具体步骤

选择基准值：从数组中选择一个元素作为基准值。常见的选择方法有选择第一个元素、最后一个元素或中间元素。
划分操作：通过交换元素，将数组分为两部分，使得左边部分的元素都小于等于基准值，右边部分的元素都大于等于基准值。
递归排序：对左右两部分分别递归地进行上述操作，直到子数组的大小为 1 或 0，此时数组已经有序。

Java 中快速排序的使用方法

代码示例

public class QuickSort {

    // 划分函数
    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++;

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

        // 交换 arr[i + 1] 和 arr[high]（基准值）
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    // 快速排序主函数
    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // pi 是划分点，arr[pi] 现在在正确的位置上
            int pi = partition(arr, low, high);

            // 递归地对划分点的左右两部分进行排序
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        System.out.println("原始数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        quickSort(arr, 0, arr.length - 1);

        System.out.println("\n排序后的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

代码说明

partition 方法：该方法负责选择基准值并进行划分操作。它遍历数组，将小于等于基准值的元素交换到左边，大于基准值的元素留在右边。最后返回划分点的索引。
quickSort 方法：这是快速排序的递归方法。它调用 partition 方法获取划分点，然后递归地对左右两部分进行排序。
main 方法：用于测试快速排序算法。创建一个示例数组，调用 quickSort 方法进行排序，并输出排序前后的数组。

常见实践

选择基准值的策略

固定基准值：选择数组的第一个元素、最后一个元素或中间元素作为基准值。这种方法简单，但在某些特殊情况下（如数组已经有序）性能较差。
随机基准值：随机选择一个元素作为基准值可以避免最坏情况的出现，提高算法的平均性能。

优化递归深度

在递归调用时，可以通过一些方法减少递归深度，提高性能。例如，当子数组的大小较小时（如小于某个阈值），可以使用插入排序等简单排序算法进行排序。

最佳实践

避免最坏情况

为了避免快速排序的最坏情况（即数组已经有序时的 $O(n^2)$ 时间复杂度），可以采用随机化基准值选择策略。例如：

private static int partition(int[] arr, int low, int high) {
    // 随机选择一个基准值
    int randomIndex = low + (int) (Math.random() * (high - low + 1));
    int pivot = arr[randomIndex];

    // 将随机选择的基准值与最后一个元素交换
    int temp = arr[randomIndex];
    arr[randomIndex] = arr[high];
    arr[high] = temp;

    // 划分操作与之前相同
    int i = (low - 1);
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;

            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1;
}

减少不必要的交换

可以通过使用三向切分（Dutch National Flag Algorithm）来减少元素的交换次数，特别是在数组中存在大量重复元素的情况下。三向切分将数组分为三部分：小于基准值、等于基准值和大于基准值。

小结

快速排序是一种高效的排序算法，在 Java 中实现快速排序需要理解其核心概念和递归过程。通过合理选择基准值、优化递归深度以及采用最佳实践，可以提高快速排序的性能，避免最坏情况的出现。希望本文能帮助读者深入理解并高效使用 Java 中的快速排序代码。

参考资料

《算法导论》（Introduction to Algorithms）
维基百科 - 快速排序
GeeksforGeeks - Quick Sort