深入理解Java中的快速排序（Quicksort）代码

简介

快速排序（Quicksort）是一种高效的排序算法，由英国计算机科学家托尼·霍尔（Tony Hoare）在1959年发明，并于1961年发表。它的平均时间复杂度为O(n log n)，最坏情况为O(n^2)，但通过一些优化策略可以尽量避免最坏情况的发生。在Java编程中，快速排序是一种常用的排序算法，理解其原理和实现对于提高程序性能至关重要。

基础概念

快速排序是一种分治算法。其基本思想是选择一个基准值（pivot），将数组分为两部分，使得左边部分的元素都小于等于基准值，右边部分的元素都大于等于基准值。然后对左右两部分分别进行递归排序，直到整个数组有序。

步骤

选择基准值：从数组中选择一个元素作为基准值。常见的选择方法有选择第一个元素、中间元素或随机选择元素作为基准值。
划分操作：通过交换元素，将数组分为两部分，左边部分的元素都小于等于基准值，右边部分的元素都大于等于基准值。
递归排序：对左右两部分分别进行递归的快速排序，直到子数组的大小为1或0（即数组已经有序）。

使用方法

在Java中实现快速排序，通常需要定义一个递归方法来完成排序操作。以下是一个简单的快速排序实现框架：

public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 划分操作，返回基准值的最终位置
            int pi = partition(arr, low, high);

            // 对基准值左边的子数组进行递归排序
            quickSort(arr, low, pi - 1);
            // 对基准值右边的子数组进行递归排序
            quickSort(arr, pi + 1, high);
        }
    }

    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;
    }

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

代码解释

quickSort方法：递归地对数组进行快速排序。首先检查low是否小于high，如果是，则调用partition方法获取基准值的最终位置pi，然后对左右两部分分别进行递归排序。
partition方法：实现划分操作。选择数组的最后一个元素作为基准值，通过遍历数组，将小于等于基准值的元素交换到左边，最后将基准值与i + 1位置的元素交换，返回基准值的最终位置。
main方法：测试快速排序算法，定义一个示例数组并调用quickSort方法进行排序，最后输出排序后的数组。

常见实践

随机选择基准值

为了避免快速排序在最坏情况下的性能下降，通常采用随机选择基准值的方法。以下是修改后的partition方法，随机选择基准值：

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

    // 将基准值与最后一个元素交换
    int temp = arr[pivotIndex];
    arr[pivotIndex] = 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;
}

处理小数组

当子数组的大小较小时，快速排序的递归调用可能会带来额外的开销。在这种情况下，可以切换到插入排序等简单排序算法，以提高性能。以下是修改后的quickSort方法，当子数组大小小于某个阈值（例如10）时，使用插入排序：

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

private static void insertionSort(int[] arr, int low, int high) {
    for (int i = low + 1; i <= high; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= low && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

最佳实践

三路划分

对于包含大量重复元素的数组，三路划分（Dutch National Flag Problem）可以进一步提高快速排序的性能。三路划分将数组分为三部分：小于基准值、等于基准值和大于基准值的元素。以下是实现三路划分的partition方法：

private static void partition(int[] arr, int low, int high) {
    if (low >= high) return;
    int pivot = arr[low];
    int i = low - 1, j = high + 1;
    int k = low;
    while (k < j) {
        if (arr[k] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[k];
            arr[k] = temp;
            k++;
        } else if (arr[k] > pivot) {
            j--;
            int temp = arr[j];
            arr[j] = arr[k];
            arr[k] = temp;
        } else {
            k++;
        }
    }
    // 递归排序左右两部分
    quickSort(arr, low, i);
    quickSort(arr, j, high);
}

优化基准值选择

除了随机选择基准值，还可以采用“三数取中”的方法选择基准值。即选择数组的第一个、中间和最后一个元素，取这三个元素的中间值作为基准值。以下是实现“三数取中”选择基准值的代码：

private static int getPivot(int[] arr, int low, int high) {
    int mid = low + (high - low) / 2;
    if ((arr[low] <= arr[mid] && arr[mid] <= arr[high]) || (arr[high] <= arr[mid] && arr[mid] <= arr[low])) {
        return mid;
    } else if ((arr[mid] <= arr[low] && arr[low] <= arr[high]) || (arr[high] <= arr[low] && arr[low] <= arr[mid])) {
        return low;
    } else {
        return high;
    }
}

private static int partition(int[] arr, int low, int high) {
    int pivotIndex = getPivot(arr, low, high);
    int pivot = arr[pivotIndex];

    // 将基准值与最后一个元素交换
    int temp = arr[pivotIndex];
    arr[pivotIndex] = 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;
}

小结

快速排序是一种高效的排序算法，在Java编程中有着广泛的应用。通过理解其基础概念、掌握使用方法、熟悉常见实践和最佳实践，可以实现高效、稳定的快速排序算法。在实际应用中，需要根据数据的特点和需求选择合适的优化策略，以提高算法的性能。

参考资料

《算法导论》（Introduction to Algorithms），Thomas H. Cormen等著
《Effective Java》，Joshua Bloch著
维基百科 - 快速排序
GeeksforGeeks - Quicksort