#### **序言：实践中的王者，理论上的舞者**

如果说归并排序是稳定可靠的“劳模”，那么快速排序就是天赋异禀的“天才”。它在**平均情况下拥有O(n log n)的卓越性能**，且其**原地排序**（In-place）的特性使其空间效率极高。尽管存在最坏情况O(n²)的“阿喀琉斯之踵”，但通过精心的优化（如三数取中、随机化），这一弱点在实践中几乎可以被完全规避。

快速排序的核心在于“**分治**”与“**分区**”（Partitioning）。它不追求一次性构建有序序列，而是通过巧妙地选择一个“基准”（Pivot），将数组划分为两部分：一部分所有元素都小于等于基准，另一部分所有元素都大于等于基准。然后递归地对这两部分进行同样的操作。这种“大事化小”的策略，使其在处理大规模数据时展现出惊人的速度。

---

### **第一章：历史溯源——莫斯科-牛津的算法奇缘**

快速排序的故事始于1960年，当时年轻的英国计算机科学家**查尔斯·安东尼·理查德·霍尔**（C.A.R. Hoare），也就是后来被尊称为**托尼·霍尔爵士**（Sir Tony Hoare）的人，正在苏联莫斯科国立大学学习机器翻译。

为了提升俄英词典的查询效率，他需要一种能快速将单词列表排序的算法。在研究冒泡排序的低效后，他灵光一现，想到了利用“分区”的思想：先找一个词作为基准，把所有比它小的词放左边，比它大的放右边，然后再分别对左右两边做同样的事。这个朴素的想法，最终演变成了我们今天所知的快速排序。

霍尔回到英国后，在艾略特兄弟公司（Elliott Brothers Ltd）工作期间，首次在Algol 60语言中实现了该算法。由于其惊人的速度，快速排序迅速风靡全球，并成为后续几十年中最受欢迎的通用排序算法。

---

### **第二章：核心思想与数学推演**

#### **2.1 算法原理**

快速排序的核心是**分区**（Partitioning）操作：
1.  **选择基准**（Pivot） 从数组中选择一个元素作为基准（选择策略至关重要）。
2.  **分区**（Partition） 重新排列数组，使得：
    - 所有小于基准的元素都位于基准的左侧。
    - 所有大于基准的元素都位于基准的右侧。
    - 基准元素则处于其最终排序后的位置。
3.  **递归排序**：递归地对基准左侧和右侧的子数组进行快速排序。

#### **2.2 数学推演：复杂度分析**

**时间复杂度**：
- **最好情况**：每次分区都能将数组完美地一分为二。此时递推关系为 `T(n) = 2T(n/2) + O(n)`，解得 **O(n log n)**。
- **最坏情况**：每次选择的基准都是当前数组的最大值或最小值（如对已排序数组使用首/尾元素作基准）。此时递推关系退化为 `T(n) = T(n-1) + O(n)`，解得 **O(n²)**。
- **平均情况**：在随机输入下，基准元素的期望位置接近中点。经过复杂的概率分析，其平均时间复杂度为 **O(n log n)**，且常数因子非常小，通常优于归并排序。

**空间复杂度**：
- 快速排序是原地排序算法，但其递归调用会消耗栈空间。
- **最好情况**：递归树深度为 `log n`，空间复杂度为 **O(log n)**。
- **最坏情况**：递归树退化为链表，深度为 `n`，空间复杂度为 **O(n)**。
- **平均情况**：空间复杂度为 **O(log n)**。

**稳定性**：
- **快速排序是不稳定的！**
- **原因**：在分区过程中，元素会进行远距离的交换。如果存在与基准相等的元素，它们可能会被交换到基准的任意一侧，从而破坏原有的相对顺序。
- **反例**：考虑数组 `[3(a), 2, 3(b)]`，选择第一个`3(a)`作为基准。分区后可能变为 `[2, 3(b), 3(a)]`，`3(b)`跑到了`3(a)`前面。

---

### **第三章：数据推演——一步步看清“分区”魔法**

以数组 `[10, 80, 30, 90, 40, 50, 70]` 为例，选择**最后一个元素**（70）作为基准。

**初始状态**: `[10, 80, 30, 90, 40, 50, 70]`

**第一轮分区**（Pivot = 70）
- 使用双指针法（i指向小于区域末尾，j遍历）。
- j=0: `10 < 70` → i=0, swap(0,0) → `[10, 80, 30, 90, 40, 50, 70]`
- j=1: `80 > 70` → 跳过
- j=2: `30 < 70` → i=1, swap(1,2) → `[10, 30, 80, 90, 40, 50, 70]`
- j=3: `90 > 70` → 跳过
- j=4: `40 < 70` → i=2, swap(2,4) → `[10, 30, 40, 90, 80, 50, 70]`
- j=5: `50 < 70` → i=3, swap(3,5) → `[10, 30, 40, 50, 80, 90, 70]`
- 分区结束，将基准70与i+1(4)位置的80交换 → `[10, 30, 40, 50, 70, 90, 80]`
- **结果**：70已在正确位置，左子数组`[10,30,40,50]`，右子数组`[90,80]`。

**递归处理左子数组** `[10,30,40,50]` (Pivot=50)
- 分区后 → `[10,30,40,50]` （已基本有序）

**递归处理右子数组** `[90,80]` (Pivot=80)
- 分区后 → `[80,90]`

**最终合并**（无需显式合并，原地完成） → `[10, 30, 40, 50, 70, 80, 90]`

---

### **第四章：优缺点与应用场景深度剖析**

#### **4.1 优点**
1.  **平均性能卓越**：O(n log n)的时间复杂度，且常数因子极小，是实践中最快的通用排序算法。
2.  **原地排序**：空间复杂度平均为O(log n)，内存效率高。
3.  **缓存友好**：具有良好的局部性，能充分利用CPU缓存。

#### **4.2 缺点**
1.  **最坏情况性能差**：O(n²)的时间复杂度，对特定输入（如已排序数组）敏感。
2.  **不稳定**：无法保证相等元素的原始顺序。
3.  **递归开销**：深度递归可能导致栈溢出（可通过尾递归优化或迭代实现缓解）。

#### **4.3 可用场景（When to Use）**
- **通用目的的内部排序**：这是其最主要的应用场景。
- **大规模数据集**：在平均情况下，性能通常优于归并排序。
- **现代编程语言的标准库**：如Java的`Arrays.sort()`对基本类型数组就采用了**双轴快速排序**（Dual-Pivot QuickSort）的变种。

#### **4.4 不可使用场景（When NOT to Use）**
- **要求稳定性的场景**：应选择归并排序或TimSort。
- **最坏情况性能不可接受的实时系统**：应选择堆排序（最坏O(n log n)）。
- **极小规模数据**：插入排序通常更快。

---

### **第五章：Java工程实践与优化**

#### **5.1 基础递归实现**

```java
public class QuickSort {

    public static void sort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 分区操作，返回基准的正确索引
            int pivotIndex = partition(arr, low, high);
            // 递归排序基准左右两部分
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    // Lomuto分区方案（较简单）
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // 选择最后一个元素作为基准
        int i = low - 1; // i指向小于区域的末尾

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        // 将基准放到正确位置
        swap(arr, i + 1, high);
        return i + 1;
    }

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

#### **5.2 关键优化策略**

1.  **三数取中法**（Median-of-Three） 选择首、中、尾三个元素的中位数作为基准，有效避免对已排序或近乎排序数组的最坏情况。
2.  **混合排序**（Hybrid Sort） 当子数组长度小于某个阈值（如10）时，切换到插入排序，因为插入排序在小数组上更快。
3.  **尾递归优化**：对较大的子数组进行递归，对较小的子数组进行迭代，可以将最坏空间复杂度从O(n)降至O(log n)。

> **现实世界**： Java的`Arrays.sort()`对`int[]`等基本类型数组使用的是Vladimir Yaroslavskiy在2009年提出的**双轴快速排序**（Dual-Pivot QuickSort），它使用两个基准，将数组分为三部分，进一步提升了性能。

---

### **结语**

快速排序是算法设计艺术与工程实践智慧的完美结晶。从霍尔在莫斯科的灵感到今天遍布全球的代码库，它经受住了时间的考验。理解快速排序，不仅是掌握一个高效的工具，更是学习如何通过“分治”和“随机化”等思想来驯服复杂性。在2026年的技术面试中，能够手写快速排序、分析其复杂度、讨论其优缺点并提出优化方案，将是您展示顶尖算法能力的关键。

如果说归并排序是稳定可靠的“劳模”，那么快速排序就是天赋异禀的“天才”。它在平均情况下拥有O(n log n)的卓越性能，且其原地排序（In-place）的特性使其空间效率极高。尽管存在最坏情况O(n²)的“阿喀琉斯之踵”，但通过精心的优化（如三数取中、随机化），这一弱点在实践中几乎可以被完全规避。

【数据结构面试】快速排序（Quick Sort）Java实现（2026最新）：时间复杂度、空间复杂度与稳定性全解析

本文将对被誉为“20世纪十大算法之一”的快速排序（Quick Sort）进行一次全面而深入的剖析。我们将追溯其由英国计算机科学家**托尼·霍尔**（Tony Hoare）在1960年提出的划时代思想，通过严谨的数学公式推演其在最好、最坏和平均情况下的时间复杂度，并阐明其“不稳定”但高效的本质。文章包含详尽的数据一步步推演、完整的Java工程级代码示例（含多种优化策略），并深入探讨其为何成为现代编程

后端

编程语言

算法

快速排序是高效的通用排序算法，平均时间复杂度O(nlogn)，空间复杂度O(logn)。采用分治策略，通过基准元素分区实现原地排序。适用于大规模数据，但需注意最坏情况O(n²)和不稳定性。优化方法包括三数取中、随机化和混合排序等。

机器翻译

Java

2026采购季 | AI焕新·智启新局

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

【数据结构面试】快速排序（Quick Sort）Java实现（2026最新）：时间复杂度、空间复杂度与稳定性全解析-腾讯云开发者社区-腾讯云

【数据结构面试】快速排序（Quick Sort）Java实现（2026最新）：时间复杂度、空间复杂度与稳定性全解析

【数据结构面试】快速排序（Quick Sort）Java实现（2026最新）：时间复杂度、空间复杂度与稳定性全解析

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐