快速排序（Quick Sort） - 数据结构与算法-学习笔记-上海佼艾

一、算法概述

快速排序（Quick Sort）是由英国计算机科学家 Tony Hoare 于 1959 年提出的一种排序算法，并于 1961 年正式发表。它是目前实际应用中最广泛的排序算法之一，被几乎所有主流编程语言的标准库所采用（或作为重要组成部分）。快速排序之所以被称为"快速"，是因为在绝大多数实际场景中，它的性能显著优于其他 O(n log n) 级别的排序算法，如归并排序和堆排序。

快速排序的核心特征是原地排序（in-place sorting），它不需要像归并排序那样额外的 O(n) 辅助空间，这使得它在内存受限的环境中具有明显优势。同时，快速排序是一种不稳定的排序算法，这意味着相等元素的相对顺序在排序后可能会发生变化。

快速排序的广泛应用体现在方方面面：从数据库系统的大规模数据排序，到编程语言运行时库的内置排序函数（如 C 语言的 qsort、Python 的 sorted 底层 Timsort 中借鉴的分区思想），再到各种需要高效排序的场景。

核心特点：

平均时间复杂度：O(n log n) — 非常高效
最坏时间复杂度：O(n²) — 可通过随机化避免
空间复杂度：O(log n) — 原地排序，递归栈空间
稳定性：不稳定 — 相等元素会交换位置
排序方式：原地排序（in-place）

历史背景： Tony Hoare 在 1959 年学习机器翻译时，需要对俄语单词进行排序以便与已排序的英语词典进行对照。他发现归并排序对于当时内存极小的计算机来说过于耗费空间，于是设计了快速排序——这一"最实用"的排序算法。Hoare 也因此贡献在 1980 年获得了图灵奖。

二、核心思想：分治与分区

快速排序基于分治策略（Divide and Conquer），其核心思想可以概括为三个步骤：

选择基准（Pivot）：从待排序数组中选择一个元素作为"基准"元素。
分区（Partition）：将数组重新排列，使得所有小于基准的元素都放在基准左边，所有大于基准的元素都放在基准右边。分区完成后，基准元素就处于其最终的正确位置上。
递归排序：对基准左边和右边的子数组分别递归地执行上述过程，直到每个子数组的长度为 0 或 1（天然有序）。

分治策略的精妙之处在于：每次分区操作都将原问题分解为两个独立的子问题，且子问题之间不再需要合并操作（这与归并排序不同），因为基准元素已经"归位"。正是这种特性使得快速排序比归并排序更节省空间。

分治过程图解

假设我们有一个数组 [3, 6, 8, 10, 1, 2, 1]，选择最后一个元素 1 作为 pivot：

原始数组：[3, 6, 8, 10, 1, 2, 1] ← pivot = 1
分区后：[1, 1, 2] + [3, 6, 8, 10] （pivot 已归位）
左递归：[1] 和 [2] 都已有序
右递归：对 [3, 6, 8, 10] 继续选取 pivot 分区

快速排序的递归深度取决于 pivot 的选择质量。理想情况下，每次 pivot 都恰好是中位数，递归树高度为 log n；最坏情况下，每次 pivot 都是最大或最小值，递归树高度为 n。

三、分区算法详解

分区（Partition）是快速排序的核心操作，不同的分区方案直接影响算法的性能和正确性。最经典的分区方案有 Lomuto 分区和 Hoare 分区两种。

3.1 Lomuto 分区方案

Lomuto 分区由 Nico Lomuto 提出，思路直观且易于理解。它通常选择最后一个元素作为 pivot，使用两个指针 i 和 j 遍历数组：

指针 j 从左向右遍历，发现小于 pivot 的元素就与指针 i 指向的元素交换，然后 i 前进一位
遍历结束后，将 pivot（位于 right 位置）与 i 指向的元素交换
最终 i 的位置就是 pivot 的正确位置

# Lomuto 分区方案
def lomuto_partition(arr, low, high):
    pivot = arr[high]          # 选择最后一个元素作为 pivot
    i = low - 1                 # i 指向小于 pivot 的区域的末尾

    for j in range(low, high):
        if arr[j] <= pivot:     # 当前元素 <= pivot
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]  # pivot 归位
    return i + 1               # 返回 pivot 的最终索引

Lomuto 分区特点：

实现简单直观，适合教学和理解
每次分区需要做 n-1 次比较
当数组中有大量重复元素时，会进行很多不必要的交换
对于已排序数组（选择末尾元素作为 pivot），性能退化到 O(n²)

3.2 Hoare 分区方案

Hoare 分区是 Tony Hoare 在原始论文中提出的方案，比 Lomuto 分区更高效。它使用两个指针从两端向中间移动：

左指针从左向右找第一个大于 pivot 的元素
右指针从右向左找第一个小于 pivot 的元素
交换这两个元素，然后继续移动
当左右指针相遇时，分区完成

Hoare 分区的平均交换次数只有 Lomuto 分区的约 1/3，这是其性能优势的主要来源。

# Hoare 分区方案（原始版本）
def hoare_partition(arr, low, high):
    pivot = arr[low]            # 选择第一个元素作为 pivot
    i = low - 1
    j = high + 1

    while True:
        # 从左向右找第一个 >= pivot 的元素
        i += 1
        while arr[i] < pivot:
            i += 1

        # 从右向左找第一个 <= pivot 的元素
        j -= 1
        while arr[j] > pivot:
            j -= 1

        if i >= j:
            return j      # 返回分区点

        arr[i], arr[j] = arr[j], arr[i]  # 交换

Hoare 分区特点：

平均交换次数少，性能优于 Lomuto 分区
返回的分区点 j 不是 pivot 的最终位置，而是左右子数组的分界
同等条件下比 Lomuto 分区快约 2~3 倍
实现略复杂，边界条件需要仔细处理

3.3 Lomuto 与 Hoare 对比

对比维度	Lomuto 分区	Hoare 分区
实现复杂度	简单易懂	稍微复杂
交换次数	较多（约 n 次）	较少（约 n/3 次）
返回值的含义	pivot 的最终位置	小于 pivot 的区域的右边界
对重复元素的处理	效率低，交换多	相对更好
对已排序数组（固定 pivot）	退化为 O(n²)	退化为 O(n²)
工程应用	教学常用，实际较少	多数标准库实现采用

四、Pivot 选择策略

Pivot 的选择是决定快速排序性能的关键因素。一个好的 pivot 能让数组被均匀地分成两半，使递归深度最小化。以下是几种常见的 pivot 选择策略。

4.1 固定位置选择

最简单的方法：总是选择第一个、最后一个或中间位置的元素作为 pivot。这种方法在完全随机的数据上表现尚可，但在特定数据分布下会严重退化。例如，总是选择最后一个元素作为 pivot 时，对已排序数组的复杂度会退化为 O(n²)。

4.2 随机选择

随机选择一个元素作为 pivot，这是最常用的优化方法。随机化使得算法对任何输入都以很高的概率达到 O(n log n) 的性能。

# 随机化快速排序
import random

def randomized_partition(arr, low, high):
    # 随机选择一个索引，与最后一个元素交换
    rand_idx = random.randint(low, high)
    arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
    return lomuto_partition(arr, low, high)

随机化 pivot 选择使得快速排序在期望意义上达到 O(n log n)，对于任何输入，算法退化到 O(n²) 的概率趋近于零。这是实际工程中最常用的策略之一。

4.3 三数取中法（Median-of-Three）

在数组的第一个、中间和最后一个元素中选择中位数作为 pivot。这种方法在不引入随机性的情况下，大幅降低了最坏情况发生的概率：

# 三数取中法选择 pivot
def median_of_three(arr, low, high):
    mid = (low + high) // 2
    # 将 low, mid, high 三个位置的元素排序
    if arr[low] > arr[mid]:
        arr[low], arr[mid] = arr[mid], arr[low]
    if arr[mid] > arr[high]:
        arr[mid], arr[high] = arr[high], arr[mid]
    if arr[low] > arr[mid]:
        arr[low], arr[mid] = arr[mid], arr[low]
    # 此时 arr[mid] 就是中位数，将其放到 high-1 位置
    arr[mid], arr[high - 1] = arr[high - 1], arr[mid]
    return arr[high - 1]

三数取中法对已排序或接近已排序的数组效果非常好，因为此时中位数接近真实的中间值，能够保证均匀的分区。Intel 的 C++ 编译器中的 qsort 实现就采用了这种方法。

更进一步的策略： 对于更大规模的数据，还有"九数取中"（median-of-nine）策略——从数组中采样 9 个元素，取其中位数作为 pivot。这种策略进一步降低了最坏情况的概率，但增加了一定的选择开销。

五、复杂度分析

5.1 最好情况

每次选择的 pivot 都是数组的中位数，将数组均匀分成两个大小相等的子数组。这种情况下：

T(n) = 2T(n/2) + O(n)
     = O(n log n)

递归树的高度为 log₂n，每层需要 O(n) 的时间进行分区，总时间复杂度为 O(n log n)。

5.2 最坏情况

每次选择的 pivot 都是数组中的最大值或最小值，导致每次分区后一个子数组为空，另一个子数组大小为 n-1。这种情况发生在：数组已排序且固定选择第一个或最后一个元素作为 pivot 时。

T(n) = T(n-1) + O(n)
     = T(n-2) + O(n-1) + O(n)
     = ...
     = O(n²)

递归树退化为一条链，深度为 n，总比较次数为 n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²)。

5.3 平均情况

对于随机排列的数据，快速排序的期望时间复杂度为 O(n log n)。直观理解：即使每次分区都产生 9:1 的极不均衡划分，递归树的深度仍然是 O(log n)，因此时间复杂度保持 O(n log n)。

严格证明概要： 快速排序的平均时间复杂度可以通过递推关系 T(n) = (1/n) * Σ_{k=0}^{n-1} [T(k) + T(n-1-k)] + cn 求解，其中 k 是分区后左子数组的大小。通过数学归纳法可以证明 T(n) ≤ cn log₂n + dn，即 O(n log n)。

5.4 空间复杂度

快速排序是原地排序算法，空间复杂度主要来自递归调用栈：

最好情况：O(log n) — 递归深度为 log n
最坏情况：O(n) — 递归深度为 n
经过尾递归优化：O(log n) — 将最坏情况的递归深度控制在 log n

指标	最好情况	平均情况	最坏情况
时间复杂度	O(n log n)	O(n log n)	O(n²)
空间复杂度	O(log n)	O(log n)	O(n)
比较次数	~n log₂n	~1.39n log₂n	n(n-1)/2
交换次数	~0.5n log₂n	~n log₂n	n(n-1)/2

六、随机化快速排序

随机化快速排序（Randomized Quicksort）通过随机选择 pivot 来避免最坏情况的发生。其核心思想是：将"选择固定位置 pivot"改为"随机选择 pivot"，从而在概率意义上保证 O(n log n) 的性能。

# 随机化快速排序完整实现
import random

def randomized_quicksort(arr, low, high):
    if low < high:
        # 随机分区
        pi = randomized_partition(arr, low, high)
        # 递归排序左右两部分
        randomized_quicksort(arr, low, pi - 1)
        randomized_quicksort(arr, pi + 1, high)

def randomized_partition(arr, low, high):
    rand_idx = random.randint(low, high)
    arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
    return lomuto_partition(arr, low, high)

随机化的意义：

任何输入导致最坏情况的概率变为 1/n!（阶乘分之一），实际上不可能发生
不需要对输入数据的分布做任何假设，算法对所有输入一视同仁
这是"随机化算法"的经典例证——通过引入随机性来消除对手（adversarial）输入的影响

随机化快速排序的期望时间复杂度为 O(n log n)，且这个期望是对算法内部随机选择的期望，而不是对输入分布的平均。这意味着无论输入是什么，算法的期望运行时间都是 O(n log n)。这是随机化算法区别于概率分析的本质所在。

七、三路快排（重复元素优化）

当数组中包含大量重复元素时，标准的快速排序会将所有等于 pivot 的元素随意分配到左右两侧，导致许多不必要的比较和交换。三路快排（Three-Way Quicksort / Dutch National Flag Problem）将数组划分为三个区域：小于 pivot、等于 pivot、大于 pivot。

7.1 荷兰国旗问题

三路分区也称为"荷兰国旗问题"（Dutch National Flag Problem），由 Edsger Dijkstra 提出。它将数组分为三部分，就像荷兰国旗的三色条纹：

# 三路快排（Dutch National Flag 分区）
def three_way_quicksort(arr, low, high):
    if low >= high:
        return

    # 三路分区
    pivot = arr[low]
    lt = low        # arr[low+1 ... lt] < pivot
    gt = high       # arr[gt ... high] > pivot
    i = low + 1     # arr[lt+1 ... i-1] == pivot

    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
            # 注意：这里 i 不递增，因为交换过来的元素还没处理
        else:  # arr[i] == pivot
            i += 1

    # 递归排序小于 pivot 和大于 pivot 的部分
    three_way_quicksort(arr, low, lt - 1)
    three_way_quicksort(arr, gt + 1, high)

7.2 性能分析

三路快排的优越性在使用随机化 pivot 时尤为明显：

所有元素都是唯一值：三路快排退化为标准快排，性能略低（因为多了一次等于的比较）
所有元素都相同：只需要一次分区，时间复杂度 O(n) — 标准快排则会退化为 O(n²)
大量重复元素：不需要递归处理等于 pivot 的区域，显著减少递归深度

工程实践： Python 的 Timsort（Python 内置排序算法）并不是三路快排，但三路快排的思想被 Java 的 Dual-Pivot QuickSort（JDK 7+ 的 Arrays.sort 对基本类型使用的算法）所借鉴。Dual-Pivot QuickSort 使用两个 pivot 将数组分为三个区域，在大量重复元素和小规模数据上表现优异。

八、快速排序的优化技巧

在实际工程中，纯粹的快速排序需要经过多项优化才能达到最佳性能。以下是几种最重要的优化手段：

8.1 小数组使用插入排序

当子数组规模较小时（通常 n < 10~20），递归调用的开销（函数调用、栈操作）超过了排序本身的计算成本。此时使用插入排序可以显著提升性能：

# 优化版快速排序：小数组用插入排序
def insertion_sort(arr, low, high):
    for i in range(low + 1, high + 1):
        key = arr[i]
        j = i - 1
        while j >= low and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

def optimized_quicksort(arr, low, high):
    if low >= high:
        return

    # 小数组使用插入排序
    if high - low < 15:
        insertion_sort(arr, low, high)
        return

    pi = median_of_three_partition(arr, low, high)
    optimized_quicksort(arr, low, pi - 1)
    optimized_quicksort(arr, pi + 1, high)

经验值显示：当阈值设为 10~20 时效果最佳。小于这个范围，插入排序的 O(n²) 行为在极小的 n 下完全被其低常数因子所弥补。

8.2 尾递归优化

快速排序是递归算法，递归深度可能达到 O(n)。通过尾递归优化，可以强制先处理较短的子数组，将递归深度控制在 O(log n)：

# 尾递归优化：始终先处理较短的子数组
def tail_recursive_quicksort(arr, low, high):
    while low < high:
        pi = partition(arr, low, high)

        # 先递归处理较短的子数组
        if pi - low < high - pi:
            tail_recursive_quicksort(arr, low, pi - 1)
            low = pi + 1  # 循环处理右半部分
        else:
            tail_recursive_quicksort(arr, pi + 1, high)
            high = pi - 1  # 循环处理左半部分

这种优化确保递归深度不超过 log₂n，从根本上避免了栈溢出风险。这也是 C 语言的 qsort 标准实现所采用的技术之一。

8.3 三数取中 + 小数组插入排序 + 尾递归（综合优化）

# 综合多种优化的快速排序
def quick_sort(arr):
    _quick_sort(arr, 0, len(arr) - 1)

def _quick_sort(arr, low, high):
    while low < high:
        # 小数组使用插入排序
        if high - low < 16:
            insertion_sort(arr, low, high)
            return

        # 三数取中 + Hoare 分区
        mid = (low + high) // 2
        if arr[low] > arr[mid]:
            arr[low], arr[mid] = arr[mid], arr[low]
        if arr[mid] > arr[high]:
            arr[mid], arr[high] = arr[high], arr[mid]
        if arr[low] > arr[mid]:
            arr[low], arr[mid] = arr[mid], arr[low]

        # 使用中位数作为 pivot 进行 Hoare 分区
        pivot = arr[mid]
        i, j = low - 1, high + 1
        while True:
            i += 1
            while arr[i] < pivot:
                i += 1
            j -= 1
            while arr[j] > pivot:
                j -= 1
            if i >= j:
                break
            arr[i], arr[j] = arr[j], arr[i]

        # 尾递归优化：先递归处理较短的子数组
        if j - low < high - j:
            _quick_sort(arr, low, j)
            low = j + 1
        else:
            _quick_sort(arr, j + 1, high)
            high = j

以上综合优化版本融合了三种经典优化策略，是工程级快速排序的典型实现。许多标准库的排序函数都采用了类似的优化组合。

优化效果总结： 经过上述优化后，快速排序的最坏情况时间复杂度仍为 O(n²)，但实际发生的概率极低（需要 pivot 选择持续失败且尾递归优化无法缓解的极端情况）。在实际应用中，优化后快速排序的运行时间相比未优化版本可减少 30%~50%。

九、快速排序的不稳定性

快速排序是一种不稳定的排序算法。稳定性的定义是：排序前后，相等元素的相对顺序保持不变。快速排序的不稳定性源于分区过程中的交换操作。

不稳定性成因

以 Lomuto 分区为例，考虑数组 [(a,1), (b,1), (c,2)]，其中括号内为（元素, 原始索引），pivot 选择最后一个元素 (c,2)：

j 指向 (a,1) → 小于 pivot，i 移到 0，交换 arr[0] 与 arr[0]（自身，不变）
j 指向 (b,1) → 小于 pivot，i 移到 1，交换 arr[1] 与 arr[1]（自身，不变）
遍历结束，交换 pivot 到位置 2：arr[2] 与 arr[high] 交换

这个例子没有体现出不稳定。但考虑以下情况：数组 [5(a), 3, 5(b)] 其中 5(a) 和 5(b) 相等但带不同标记：

选择 pivot = 3（假设在中间位置，需要先交换到末尾）
分区过程中 5(a) 和 5(b) 的相对顺序在后续与更小元素的交换中可能被改变

实际影响： 不稳定排序意味着当你对已按某个字段排序的数据再按另一字段排序时，第一次排序的顺序会被打乱。如果稳定性对你的应用场景至关重要（如数据库的多级排序），应考虑归并排序或插入排序等稳定排序算法。

十、完整实现与测试

以下是一个完整且功能完善的快速排序实现，包含随机化选 pivot、综合优化策略，以及测试用例：

# ============================================
# 快速排序完整工程实现
# ============================================
import random
import time

class QuickSort:
    """快速排序封装类"""

    def __init__(self, arr, pivot_strategy='random'):
        self.arr = arr[:]       # 复制一份，不修改原数组
        self.comparisons = 0   # 计数比较次数
        self.swaps = 0          # 计数交换次数
        self.strategy = pivot_strategy
        self._sort(0, len(self.arr) - 1)

    def _sort(self, low, high):
        while low < high:
            # 小数组优化
            if high - low < 15:
                self._insertion_sort(low, high)
                return

            # 分区
            pi = self._partition(low, high)

            # 尾递归优化
            if pi - low < high - pi:
                self._sort(low, pi - 1)
                low = pi + 1
            else:
                self._sort(pi + 1, high)
                high = pi - 1

    def _partition(self, low, high):
        # 根据策略选择 pivot
        if self.strategy == 'random':
            idx = random.randint(low, high)
            self.arr[idx], self.arr[high] = \
                self.arr[high], self.arr[idx]
        elif self.strategy == 'median3':
            mid = (low + high) // 2
            if self.arr[low] > self.arr[mid]:
                self._swap(low, mid)
            if self.arr[low] > self.arr[high]:
                self._swap(low, high)
            if self.arr[mid] > self.arr[high]:
                self._swap(mid, high)
            self.arr[mid], self.arr[high] = \
                self.arr[high], self.arr[mid]

        pivot = self.arr[high]
        i = low - 1

        for j in range(low, high):
            self.comparisons += 1
            if self.arr[j] <= pivot:
                i += 1
                self._swap(i, j)

        self._swap(i + 1, high)
        return i + 1

    def _swap(self, i, j):
        self.arr[i], self.arr[j] = self.arr[j], self.arr[i]
        self.swaps += 1

    def _insertion_sort(self, low, high):
        for i in range(low + 1, high + 1):
            key = self.arr[i]
            j = i - 1
            while j >= low and self.arr[j] > key:
                self.comparisons += 1
                self.arr[j + 1] = self.arr[j]
                self.swaps += 1
                j -= 1
            self.arr[j + 1] = key

    def get_result(self):
        """返回排序结果和统计信息"""
        return {
            'sorted': self.arr,
            'comparisons': self.comparisons,
            'swaps': self.swaps
        }


# ============================================
# 测试与验证
# ============================================
if __name__ == '__main__':
    # 测试 1：基本功能测试
    test1 = [3, 6, 8, 10, 1, 2, 1]
    qs = QuickSort(test1)
    print("原始:", test1)
    print("排序:", qs.get_result()['sorted'])
    # 输出: [1, 1, 2, 3, 6, 8, 10]

    # 测试 2：大规模随机数据
    n = 10000
    large = [random.randint(0, 1000) for _ in range(n)]
    start = time.time()
    qs2 = QuickSort(large)
    elapsed = time.time() - start
    print(f"n={n}, 用时={elapsed:.4f}s, 比较={qs2.get_result()['comparisons']}, 交换={qs2.get_result()['swaps']}")

    # 测试 3：已排序数据
    sorted_arr = list(range(1000))
    qs3 = QuickSort(sorted_arr)
    print("已排序数据验证通过:", qs3.get_result()['sorted'] == sorted(sorted_arr))

    # 测试 4：全部相同的数据
    same = [5] * 100
    qs4 = QuickSort(same)
    print("全同数据验证通过:", qs4.get_result()['sorted'] == sorted(same))

十一、快速排序与其它排序算法的对比

算法	平均时间	最坏时间	空间	稳定	适用场景
快速排序	O(n log n)	O(n²)	O(log n)	否	通用排序，大数据量
归并排序	O(n log n)	O(n log n)	O(n)	是	需要稳定排序，链表排序
堆排序	O(n log n)	O(n log n)	O(1)	否	内存极受限的环境
插入排序	O(n²)	O(n²)	O(1)	是	小规模数据，近有序数据
桶排序	O(n+k)	O(n²)	O(n+k)	是	数据服从均匀分布

为什么快速排序最实用？

在绝大多数数据分布下，快速排序的实际运行时间比堆排序和归并排序快 2~3 倍（常数因子更小）
快速排序是原地算法，内存占用仅为 O(log n)，比归并排序的 O(n) 大幅节省内存
经过优化的快速排序（随机化 + 三数取中 + 小数组插入排序 + 尾递归优化）在各种场景下都表现稳定

十二、核心要点总结

快速排序要点速查：

核心思想： 分治 + 分区。选取 pivot → 分区 → 递归排序左右子数组
Lomuto 分区： 实现简单，适合教学；Hoare 分区：效率更高，适合工程应用
Pivot 选择： 随机选择和三数取中法是最常用的两种策略，有效避免最坏情况
时间复杂度： 平均 O(n log n)，最坏 O(n²)，随机化后期望 O(n log n)
空间复杂度： O(log n) 原地排序，经过尾递归优化后最坏 O(log n)
三路快排： 处理大量重复元素时效率极高，将等于 pivot 的元素集中处理
不稳定性： 快速排序是不稳定排序，分区操作会打乱相等元素的相对顺序
工程优化： 小数组用插入排序 + 三数取中 pivot + 尾递归优化 = 工业级快速排序

学习建议： 快速排序是面试中考察频率最高的排序算法之一。建议掌握：① 手写 Lomuto 分区和 Hoare 分区；② 能够分析最好/最坏/平均时间复杂度；③ 理解随机化 pivot 的原理；④ 掌握三路快排的写法。在实际编码中，建议使用随机化 pivot + 三路分区（对重复元素友好）+ 小数组插入排序的组合方案。

十三、进一步思考

快速排序虽然经典，但算法领域仍在不断演进：

双轴快速排序（Dual-Pivot QuickSort）： Java 的 Arrays.sort() 使用两个 pivot 进行分区，进一步减少了比较次数，性能比经典快排提升约 10~20%
内省排序（IntroSort）： C++ std::sort 的行为，结合了快速排序、堆排序和插入排序三者的优势：开始时使用快速排序，当递归深度超过 log n 时切换到堆排序，小数组使用插入排序
并行快速排序： 在多核环境下，利用并行计算加速排序过程，对于大规模数据可获得线性加速比
快速排序与外部排序： 当数据量超出内存容量时，快速排序的分治思想可应用于外部排序（External Sorting），如与归并结合处理大规模磁盘数据

"快速排序之所以'快速'，不是因为它在理论上比其他排序更快——毕竟大多数比较排序都有 O(n log n) 的下界——而是因为它的常数因子小、空间效率高、对缓存的利用更友好。这种理论分析与工程实践的完美结合，正是算法之美的体现。"