Python常见排序算法实现：冒泡、快速与归并排序代码

在 Python 程序开发与数据结构学习中，排序是最基础也最关键的操作之一。虽然日常业务开发可以直接使用 Python 内置的高效 sort() 或 sorted() 函数（底层基于结合了归并与插入的 Timsort），但深入理解冒泡排序、快速排序与归并排序这三种经典算法的代码实现机制、时间空间复杂度边界以及核心算法思想，是掌握算法设计和编写高性能代码的必修课。本文直接提供这三种算法在 Python 中的规范完整代码，并通过步骤拆解与特性对照，帮助读者清晰建立排序算法的选型认知。

一、冒泡排序（Bubble Sort）：相邻比较与提前终止优化

冒泡排序是一种直观的比较类排序算法。其基本逻辑是：遍历待排序列表，依次比较相邻的两个元素；若前一个元素大于后一个元素，则将其互换位置。每一趟遍历结束后，当前未排序区间中数值最大的元素便会如同水底气泡一般“浮动”至右侧最终位置。

传统冒泡排序无论输入数据是否已有序，都会执行完整的两层循环，耗费固定的 O(n²) 比较次数。在工程实现中，最实用的改进是引入一个布尔标志位 swapped：如果某一整趟相邻元素比较中没有发生任何一次位置交换，说明列表已经完全有序，此时应立即提前退出循环，将最佳情况下的时间复杂度降低到 O(n)。

1. 冒泡排序完整 Python 代码

def bubble_sort(arr: list) -> list:
    """
    优化版冒泡排序实现（带提前终止标志）
    :param arr: 待排序列表
    :return: 原地排序后的列表
    """
    n = len(arr)
    # 外层循环控制遍历轮数，共需要 n - 1 轮
    for i in range(n - 1):
        swapped = False
        # 内层循环进行相邻元素比较，每轮后末尾 i 个元素已就位
        for j in range(0, n - 1 - i):
            if arr[j] > arr[j + 1]:
                # 相邻元素逆序，就地交换
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        # 若整轮遍历没有发生交换，说明已有序，提前结束
        if not swapped:
            break
    return arr


# 验证与测试
if __name__ == "__main__":
    sample_data = [64, 34, 25, 12, 22, 11, 90]
    print("排序前:", sample_data)
    result = bubble_sort(sample_data)
    print("排序后:", result)

二、快速排序（Quick Sort）：分治思想与双指针原地划分

快速排序是目前应用最广泛的基于比较的高效排序算法之一，核心在于分而治之（Divide and Conquer）策略。其执行步骤分为三步：

1. 选取基准（Pivot）：从序列中选择一个元素作为基准值（通常选取首元素、尾元素或三数取中值）。
2. 划分（Partition）：重排序列，将所有比基准值小的元素移动到其左侧，比基准值大的元素移动到其右侧。此过程完成后，基准值所在位置即为其最终有序位置。
3. 递归子区间：分别对基准值左侧与右侧的子区间递归执行快速排序，直至区间长度为 0 或 1。

1. 关键做法对比：列表推导式写法 vs 原地双指针分区

在 Python 中实现快速排序常有两种不同写法，理解两者的关键差异极其重要：

• 列表推导式直观写法（Out-of-place）：利用 [x for x in arr if x < pivot] 过滤出左右子列表拼接。这种方式代码极简、逻辑清晰，但每一层递归都创建了多个新列表对象，额外空间开销达到 O(n log n)，且伴随大量的 Python 内存分配与垃圾回收耗时。
• 双指针原地分区写法（In-place）：通过维护下标索引直接在原始列表上进行数据互换，无需开辟任何新的列表空间，额外空间仅保留递归调用栈所需的 O(log n)。对于大规模数据处理，原地分区才是真正符合算法工程规范的实现。

2. 快速排序完整 Python 代码（规范原地划分）

def partition(arr: list, low: int, high: int) -> int:
    """
    对区间 [low, high] 执行原地分区，以 arr[high] 为基准值
    """
    pivot = arr[high]
    i = low - 1  # i 为小于 pivot 区域的边界指针
    
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
            
    # 将基准值放到边界右侧的最终位置
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1


def quick_sort_inplace(arr: list, low: int = 0, high: int = None) -> list:
    """
    原地快速排序主函数
    :param arr: 待排序列表
    :param low: 子区间起始下标
    :param high: 子区间结束下标
    :return: 原地排序后的列表
    """
    if high is None:
        high = len(arr) - 1
        
    if low < high:
        # 划分并获取基准值索引
        pivot_index = partition(arr, low, high)
        # 递归排序左半部分和右半部分
        quick_sort_inplace(arr, low, pivot_index - 1)
        quick_sort_inplace(arr, pivot_index + 1, high)
    return arr


# 验证与测试
if __name__ == "__main__":
    raw_list = [38, 27, 43, 3, 9, 82, 10]
    print("排序前:", raw_list)
    quick_sort_inplace(raw_list)
    print("排序后:", raw_list)

三、归并排序（Merge Sort）：分治递归与稳定合并

归并排序同样基于分治思想，但与快速排序“先分区再递归”的自顶向下方式不同，归并排序采取“先无脑二分拆解，再自底向上有序合并”的路径。由于两个已经有序的子序列可以在 O(n) 线性时间内合并为一个整体有序序列，因此整棵二叉拆分树的高度恒为 log₂ n，无论数据初始排列如何，归并排序的时间复杂度始终稳定在 O(n log n)。

1. 归并排序完整 Python 代码

def merge_sort(arr: list) -> list:
    """
    归并排序实现
    :param arr: 待排序列表
    :return: 全新创建的升序排序列表
    """
    # 递归基准条件：当列表长度小于等于 1 时天然有序
    if len(arr) <= 1:
        return arr

    # 计算中间位置，切分序列
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    # 合并两个有序子序列
    return merge(left_half, right_half)


def merge(left: list, right: list) -> list:
    """
    双指针线性归并两个有序序列
    """
    merged = []
    i = j = 0

    # 双指针遍历两段子序列，依次挑取较小元素放入新列表
    while i < len(left) and j < len(right):
        # 使用 <= 确保两个相同元素时优先选取左侧元素，保证算法稳定性
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1

    # 追加剩余未遍历完的元素
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged


# 验证与测试
if __name__ == "__main__":
    nums = [12, 11, 13, 5, 6, 7]
    print("排序前:", nums)
    sorted_nums = merge_sort(nums)
    print("排序后:", sorted_nums)

四、核心机制与场景差异深度对比

为了在实际开发中做出正确的算法取舍，我们需要在相同的一组衡量维度下，深入审视三种算法的物理特征与工程影响。

1. 为什么“稳定性”在工程中如此重要？

许多初学者容易忽视排序的“稳定性”。假设有一个用户订单列表，每个订单包含“下单时间”和“支付金额”两个属性。业务需求要求：优先按支付金额降序排列；如果金额完全相同，则保持原有的下单时间先后顺序。

• 如果使用归并排序（稳定），我们只需先按时间排序，再按金额排序，第二次排序绝对不会破坏相同金额下的时间顺序。
• 如果使用快速排序（不稳定），快速排序在分区过程中为了将元素赶往左右两侧，会跨越很长距离进行交换，这会直接打乱金额相同订单的最初时间顺序，导致需要额外的二级键比对逻辑。

2. 原地快速排序与归并排序的物理性能取舍

尽管快速排序和归并排序的平均时间复杂度都是 O(n log n)，但在内存内对普通数组排序时，快速排序通常明显快于归并排序。这是因为：

1. CPU 缓存局部性（Cache Locality）：快速排序的原地双指针是从两端向中间连续扫描，高度契合现代 CPU 的缓存行预取机制；而归并排序频繁创建新数组切片，造成更多的缓存失效和内存分配开销。
2. 空间压力：在受限内存环境中，若待排序数组大小达到数千万，快速排序只需占用极小的递归栈内存（O(log n)），而归并排序需要额外分配大小相同的 O(n) 内存，极易引发内存溢出。

五、总结与实战选型建议

通过本文对三种算法原理与 Python 代码实现的剖析，可以提炼出如下实战选型指南：

• 教学理解与小微数据检查：优先阅读和实现冒泡排序。配合 swapped 标志，能够深刻理解相邻比较的本质及最佳情况剪枝。
• 常规内存数据高性能排序：采用快速排序（原地划分）。其平均运行速度极快，空间开销微乎其微，注意配合三数取中或随机选择基准防止恶化。
• 严苛时间界限与稳定多键排序：采用归并排序。其 O(n log n) 的时间上界不受输入数据排列影响，且天然具备保序特性，亦是海量数据外部排序的核心模式。
• Python 生产环境实战：在无需手写算法的真实 Python 项目中，直接调用内置的 list.sort() 或 sorted()。Python 底层的 Timsort 巧妙地将归并排序对有序分段的高效利用与插入排序在小数组上的低开销融为一体，兼具稳定性与工业级极致性能。