快速排序算法详解与 Java 实现

2. 快速排序算法简介

快速排序（Quicksort）是一种基于分治思想（Divide-and-Conquer Strategy）的排序算法。它的平均时间复杂度为 *O(n log n)*，是目前最常用的排序算法之一，尤其适合处理大规模数据。

⚠️ 需要注意的是，快速排序并不是一个稳定的排序算法。所谓稳定排序是指：相同值的元素在排序后的输出中仍然保持其在输入中的相对顺序。

快速排序的核心思路是：

从数组中选择一个基准元素（pivot）
将数组划分为两部分：
- 左侧子数组：所有小于等于 pivot 的元素
- 右侧子数组：所有大于 pivot 的元素
对左右两个子数组递归执行上述过程

最终将所有已排序的子数组合并，得到完整的有序数组。

2.1 算法步骤分解

✅ 快速排序的关键操作可以总结为以下几步：

选择一个 pivot 元素
进行分区操作（partition）——将数组中小于 pivot 的元素放在左侧，大于 pivot 的放在右侧
递归地对 pivot 左右两个子数组分别执行快速排序

由于采用了分治策略，快速排序天然具有递归特性。

来看一个简单的例子，加深理解：

Arr[] = {5, 9, 4, 6, 5, 3}

假设我们选 5 作为 pivot
分区后变成 {3, 4, 5, 6, 5, 9}，此时 pivot 已经处于最终位置
再对左子数组 {3, 4} 排序（以 3 为 pivot）
没有比 3 更小的元素，继续处理右子数组 {4}
继续处理原数组右半部分 {6, 5, 9}，直到整体有序

2.2 如何选择最优的 Pivot

选择合适的 pivot 是快速排序的关键点之一。理想情况下，选择中位数作为 pivot 可以将数组均匀划分为两个等长子数组。

但是，在一个无序数组中找中位数成本太高。因此实践中常采用如下策略：

首个元素
最后一个元素 ✅（本文实现使用这个）
中间元素
随机选取

3. Java 实现代码

下面是快速排序的 Java 核心实现：

3.1 主排序方法 quickSort()

该方法接收待排序数组和起止索引：

public void quickSort(int arr[], int begin, int end) {
    if (begin < end) {
        int partitionIndex = partition(arr, begin, end);

        quickSort(arr, begin, partitionIndex-1);
        quickSort(arr, partitionIndex+1, end);
    }
}

逻辑说明：

如果 begin < end，说明还有未排序的区间
调用 partition() 方法获取 pivot 的最终位置
然后对 pivot 左右两个子数组递归排序

3.2 分区方法 partition()

本实现选择最后一个元素作为 pivot，并将小于等于 pivot 的元素移到左边：

private int partition(int arr[], int begin, int end) {
    int pivot = arr[end];
    int i = (begin-1);

    for (int j = begin; j < end; j++) {
        if (arr[j] <= pivot) {
            i++;

            int swapTemp = arr[i];
            arr[i] = arr[j];
            arr[j] = swapTemp;
        }
    }

    int swapTemp = arr[i+1];
    arr[i+1] = arr[end];
    arr[end] = swapTemp;

    return i+1;
}

分区完成后，pivot 左边都是小于等于它的元素，右边都是大于它的元素，pivot 也处于最终排序位置。

4. 性能分析

4.1 时间复杂度分析

情况	时间复杂度	说明
✅ 最好情况	O(n log n)	每次都能将数组平均分割
❌ 最坏情况	O(n²)	每次只减少一个元素，如已排序数组
📊 平均情况	O(n log n)	大多数实际场景下的表现

因此，快速排序虽然最坏情况不理想，但在平均性能上非常优秀，适合大数据量排序。

4.2 与归并排序的对比

虽然快速排序和归并排序的平均时间复杂度都是 *O(n log n)*，但它们在以下方面有显著差异：

特性	快速排序	归并排序
空间复杂度	O(log n)	O(n)
是否稳定	❌ 不稳定	✅ 稳定
数组适用性	✅ 更优	❌ 需要额外空间
链表适用性	❌ 不方便	✅ 更适合

📌 总结：

对于数组排序，快速排序更节省空间
对于链表排序，归并排序更合适（因为链表访问不是随机的）

5. 结语

快速排序是一种优雅且高效的排序算法，适用于大多数排序场景。

✅ 它是一个“原地”排序算法，平均时间复杂度为 *O(n log n)*。

值得一提的是，Java 标准库中的 Arrays.sort() 在对基本类型数组排序时就使用了优化版的快速排序（双轴快排），其性能远超我们手写的简单版本。

因此在生产环境中，建议优先使用 JDK 提供的排序方法，除非有特殊需求。

源码地址：GitHub 仓库

Persistence

REST

Security