Java 快速排序算法详解及通用实现模板案例示范-EW帮帮网

1. 引言

在众多排序算法中，快速排序（QuickSort） 是一种非常经典且高效的算法。它采用“分治法”的策略，通过递归地将数组分割成更小的部分，从而快速完成排序操作。快速排序的平均时间复杂度为 O(n log n)，在大多数情况下表现优异。

2. 快速排序的原理

快速排序的核心思想是选择一个“基准”元素，然后通过比较将数组划分为两部分：小于基准值的元素和大于基准值的元素。接下来，递归地对左右两部分进行排序，最终得到一个有序数组。

快速排序的关键步骤包括：

选择基准元素（Pivot）。
划分数组：将小于基准值的元素放在左侧，大于基准值的元素放在右侧。
递归排序左右两部分。

3. 快速排序适用问题类型

快速排序主要用于解决以下问题：

对无序数组进行排序：适用于需要高效排序的场景，如对大量数据的排序。
查找排序后的中位数或其他特定位置的元素：例如在数据集中寻找第 k 小的元素。
需要原地排序的场景：快速排序是原地排序算法，无需额外的内存空间。

4. 快速排序的通用实现模板

4.1 标准快速排序模板

下面是快速排序的标准实现：

public class QuickSort {
    /**
     * 快速排序的主方法
     * @param arr 待排序的数组
     * @param left 数组的左边界
     * @param right 数组的右边界
     */
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            // 获取基准元素的正确位置
            int pivotIndex = partition(arr, left, right);
            // 递归排序左边部分
            quickSort(arr, left, pivotIndex - 1);
            // 递归排序右边部分
            quickSort(arr, pivotIndex + 1, right);
        }
    }

    /**
     * 划分数组，将小于基准值的元素放在左边，大于基准值的放在右边
     * @param arr 待划分的数组
     * @param left 左边界
     * @param right 右边界
     * @return 基准元素的最终位置
     */
    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];  // 选择最右边的元素作为基准
        int i = left - 1;  // i是小于pivot的元素的边界

        for (int j = left; j < right; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);  // 交换小于pivot的元素到左边
            }
        }

        swap(arr, i + 1, right);  // 将pivot放到正确的位置
        return i + 1;
    }

    /**
     * 交换数组中的两个元素
     * @param arr 数组
     * @param i 元素索引 i
     * @param j 元素索引 j
     */
    private static 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[] array = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
        quickSort(array, 0, array.length - 1);
        System.out.println("排序后的数组：" + java.util.Arrays.toString(array));
    }
}

解释：

quickSort 是主函数，负责递归地对数组的左右部分进行排序。
partition 函数通过选择基准元素将数组划分为两部分。
swap 用于交换两个元素的位置。

4.2 快速排序的时间复杂度

快速排序的时间复杂度在平均情况下为 O(n log n)，这是因为每次划分时，数组被大致平分为两部分，每个元素在每层递归中最多比较一次。递归的深度为 log n，因此总的比较次数为 n log n。

在最坏情况下（当数组已经有序，且每次选择的基准是最小或最大的元素），时间复杂度会退化为 O(n²)。为了解决这个问题，可以随机选择基准元素，或者使用三数取中法（选择左、中、右三个元素的中值作为基准）来减少最坏情况发生的概率。

5. 快速排序的时序图

在这里插入图片描述

6. 案例分析：快速排序在电商系统中的应用

在电商系统中，快速排序的应用场景非常广泛，特别是在处理大规模数据时。例如：

商品价格排序：快速排序可以用来对商品价格进行排序，以便用户可以按照价格升序或降序查看商品。
订单记录排序：通过对订单的时间戳进行排序，系统可以快速找到最近的订单。
用户评分排序：对于基于用户评分的推荐系统，快速排序可以对用户评分进行排序，以便根据评分推荐商品。

案例 1：商品价格排序

假设电商系统需要对某一类别的商品价格进行排序，以便用户可以根据价格从低到高查看商品列表。以下是通过快速排序对商品价格排序的代码示例：

public class ProductPriceSort {
    public static void quickSortPrices(double[] prices, int left, int right) {
        if (left < right) {
            int pivotIndex = partition(prices, left, right);
            quickSortPrices(prices, left, pivotIndex - 1);
            quickSortPrices(prices, pivotIndex + 1, right);
        }
    }

    private static int partition(double[] prices, int left, int right) {
        double pivot = prices[right];
        int i = left - 1;

        for (int j = left; j < right; j++) {
            if (prices[j] < pivot) {
                i++;
                swap(prices, i, j);
            }
        }

        swap(prices, i + 1, right);
        return i + 1;
    }

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

    public static void main(String[] args) {
        double[] productPrices = {299.99, 499.99, 199.99, 899.99, 799.99, 100.00};
        quickSortPrices(productPrices, 0, productPrices.length - 1);
        System.out.println("排序后的商品价格：" + java.util.Arrays.toString(productPrices));
    }
}

案例 2：订单记录排序

电商系统通常会按照时间对订单进行排序，以便用户查看历史订单记录。通过对订单时间戳进行排序，用户可以方便地查看最近的订单。

public class OrderSort {
    public static void quickSortOrders(long[] orderTimes, int left, int right) {
        if (left < right) {
            int pivotIndex = partition(orderTimes, left, right);
            quickSortOrders(orderTimes, left, pivotIndex - 1);
            quickSortOrders(orderTimes, pivotIndex + 1, right);
        }
    }

    private static int partition(long[] orderTimes, int left, int right) {
        long pivot = orderTimes[right];
        int i = left - 1;

        for (int j = left; j < right; j++) {
            if (orderTimes[j] < pivot) {
                i++;
                swap(orderTimes, i, j);
            }
        }

        swap(orderTimes, i + 1, right);
        return i + 1;
    }

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

    public static void main(String[] args) {
        long[] orderTimes = {1623010200L, 1623011100L, 1623010500L, 1623010800L};
        quickSortOrders(orderTimes, 0, orderTimes.length - 1);
        System.out.println("排序后的订单时间：" + java.util.Arrays.toString(orderTimes));
    }
}

7. 快速排序的常见问题

最坏情况性能退化：当输入数组已经有序，或者每次选择的基准值是最小或最大值时，快速排序的时间复杂度会退化为 O(n²)。为了解决这个问题，可以使用三数取中法或随机选择基准值来避免这种情况。
递归过深导致栈溢出：对于非常大的数组，递归过深可能导致栈溢出。可以通过优化递归条件，或者采用尾递归优化来避免这个问题。
不稳定性：快速排序是一种不稳定排序，即相同值的元素在排序后相对顺序可能会发生变化。如果对稳定性有要求，可以考虑其他排序算法，如归并排序。

Java 快速排序算法详解及通用实现模板案例示范