Python 排序算法全解析：从冒泡到堆排，手写代码带你彻底搞懂

前言

在计算机科学的浩瀚星空中，排序算法无疑是最璀璨的基石之一。无论是数据库的索引构建、搜索引擎的结果排名，还是日常开发中的数据处理，排序都扮演着不可或缺的角色。Python 作为一门简洁优雅的编程语言，其内置的 sorted() 和 list.sort() 方法虽然强大，但作为一名优秀的开发者，深入理解其背后的算法思想——从最直观的冒泡排序到高效复杂的堆排序，是提升算法素养和解决复杂问题能力的必经之路。

本文将带你穿越时间的长河，重温经典。我们将逐一剖析十大经典排序算法的思想基础，通过详细的算法演练和手写的 Python 代码，让你不仅“知其然”，更“知其所以然”。无论你是正在备战面试的求职者，还是渴望夯实基础的初学者，这篇文章都将是你算法进阶的坚实阶梯。

第一部分：交换类排序 —— 思想的萌芽

1. 冒泡排序 (Bubble Sort)

算法思想基础：
冒泡排序是最直观的排序算法。它的核心思想是通过重复地遍历待排序序列，依次比较相邻的两个元素，如果它们的顺序错误（如前一个比后一个大），就交换它们。每一轮遍历都会将当前未排序部分中最大的元素“冒泡”到序列的末尾。

实现思路：

1. 外层循环控制遍历的轮数，共需 n-1 轮。
2. 内层循环负责两两比较，每轮结束后，最大的元素已归位，故内层循环次数逐轮递减。
3. 优化点：若某一轮遍历中没有发生任何交换，说明序列已有序，可提前终止。

算法演练：
假设序列为 [5, 1, 4, 2]

• 第一轮：[1, 4, 2, 5] (5冒泡到最后)
• 第二轮：[1, 2, 4, 5] (4冒泡到倒数第二)
• 第三轮：[1, 2, 4, 5] (无交换，结束)

具体实现代码：

文件名称：bubble_sort.py

def bubble_sort(arr):
    """
    冒泡排序实现
    时间复杂度: O(n^2), 空间复杂度: O(1)
    """
    n = len(arr)
    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__":
    data = [64, 34, 25, 12, 22, 11, 90]
    print("原始数据:", data)
    print("排序结果:", bubble_sort(data.copy()))

2. 快速排序 (Quick Sort)

算法思想基础：
快速排序是分治法（Divide and Conquer）的典型应用。它通过选择一个“基准值”（Pivot），将数组分为两部分：左边部分所有元素小于基准值，右边部分所有元素大于基准值。然后递归地对左右两部分进行同样的操作。

实现思路：

1. 选择基准：通常选择第一个、最后一个或中间的元素。
2. 分区操作 (Partition)：重新排列数组，使基准值左侧均小于它，右侧均大于它。
3. 递归求解：对基准值左右两侧的子数组递归执行上述步骤。

算法演练：
序列 [3, 6, 8, 10, 1, 2, 1]，选第一个 3 为基准。

• 分区后：[1, 2, 1] 3 [6, 8, 10]
• 递归处理左边 [1, 2, 1] 和右边 [6, 8, 10]。

具体实现代码：

文件名称：quick_sort.py

def quick_sort(arr, low=0, high=None):
    """
    快速排序实现 (原地排序版本)
    时间复杂度: 平均 O(n log n), 最坏 O(n^2)
    空间复杂度: O(log n) (递归栈)
    """
    if high is None:
        high = len(arr) - 1

    if low < high:
        # 获取分区点索引
        pivot_index = partition(arr, low, high)
        # 递归排序左半部分
        quick_sort(arr, low, pivot_index - 1)
        # 递归排序右半部分
        quick_sort(arr, pivot_index + 1, high)
    
    return arr

def partition(arr, low, 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[i], arr[j] = arr[j], arr[i]
    
    # 将基准值放到正确的位置 (i+1)
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# 测试用例
if __name__ == "__main__":
    data = [10, 7, 8, 9, 1, 5]
    print("原始数据:", data)
    print("排序结果:", quick_sort(data.copy()))

第二部分：插入类排序 —— 有序的构建

3. 直接插入排序 (Insertion Sort)

算法思想基础：
类似于整理扑克牌。将数组分为“已排序”和“未排序”两部分。每次从未排序部分取出一个元素，将其插入到已排序部分的正确位置。

实现思路：

1. 从第二个元素开始遍历（第一个元素视为已排序）。
2. 将当前元素与已排序部分的元素从后向前比较。
3. 若已排序元素大于当前元素，则将其后移一位。
4. 找到合适位置后插入。

算法演练：
序列 [4, 3, 2, 10]

• 处理 3：[3, 4, 2, 10]
• 处理 2：[2, 3, 4, 10]
• 处理 10：[2, 3, 4, 10] (位置不变)

具体实现代码：

文件名称：insertion_sort.py

def insertion_sort(arr):
    """
    直接插入排序
    时间复杂度: O(n^2), 空间复杂度: O(1)
    适用于小规模或基本有序的数据
    """
    for i in range(1, len(arr)):
        key = arr[i]  # 当前要插入的元素
        j = i - 1
        
        # 将大于 key 的元素向后移动
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        # 插入 key 到正确位置
        arr[j + 1] = key
    
    return arr

# 测试用例
if __name__ == "__main__":
    data = [12, 11, 13, 5, 6]
    print("原始数据:", data)
    print("排序结果:", insertion_sort(data.copy()))

4. 希尔排序 (Shell Sort)

算法思想基础：
希尔排序是插入排序的改进版（缩小增量排序）。它先将整个待排序序列分割成若干子序列（由间隔 gap 决定），分别进行直接插入排序。随着 gap 逐渐减小，序列越来越有序，当 gap=1 时，即为最后一次标准的插入排序。

实现思路：

1. 选择一个增量序列（如 n/2, n/4, ..., 1）。
2. 按增量分组，对每组进行插入排序。
3. 缩小增量，重复步骤2，直到增量为1。

具体实现代码：

文件名称：shell_sort.py

def shell_sort(arr):
    """
    希尔排序
    时间复杂度: 取决于增量序列，平均 O(n log n) ~ O(n^1.3)
    """
    n = len(arr)
    gap = n // 2  # 初始增量
    
    while gap > 0:
        # 对每个分组进行插入排序
        for i in range(gap, n):
            temp = arr[i]
            j = i
            # 在组内进行插入排序
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        
        gap //= 2  # 缩小增量
    
    return arr

# 测试用例
if __name__ == "__main__":
    data = [23, 12, 1, 8, 34, 54, 2, 3]
    print("原始数据:", data)
    print("排序结果:", shell_sort(data.copy()))

第三部分：选择类排序 —— 极值的筛选

5. 简单选择排序 (Selection Sort)

算法思想基础：
每一轮从未排序的部分中选择最小（或最大）的元素，放到已排序部分的末尾。

实现思路：

1. 外层循环控制已排序区的末尾。
2. 内层循环在未排序区寻找最小值的索引。
3. 将找到的最小值与未排序区的第一个元素交换。

具体实现代码：

文件名称：selection_sort.py

def selection_sort(arr):
    """
    简单选择排序
    时间复杂度: O(n^2), 空间复杂度: O(1)
    """
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        # 寻找未排序部分的最小值索引
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # 交换
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr

# 测试用例
if __name__ == "__main__":
    data = [64, 25, 12, 22, 11]
    print("原始数据:", data)
    print("排序结果:", selection_sort(data.copy()))

6. 堆排序 (Heap Sort)

算法思想基础：
利用堆这种数据结构（完全二叉树）设计的排序算法。堆分为大顶堆（父节点>=子节点）和小顶堆。堆排序通常使用大顶堆进行升序排序。

实现思路：

1. 建堆：将无序数组构建成一个大顶堆。
2. 交换：将堆顶元素（最大值）与数组末尾元素交换。
3. 调整：忽略末尾已排序元素，将剩余元素重新调整为大顶堆。
4. 重复步骤2-3，直到堆的大小为1。

具体实现代码：

文件名称：heap_sort.py

def heap_sort(arr):
    """
    堆排序
    时间复杂度: O(n log n), 空间复杂度: O(1)
    """
    n = len(arr)

    # 1. 构建大顶堆 (从最后一个非叶子节点开始向上调整)
    # 最后一个非叶子节点索引为 n//2 - 1
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 2. 逐个提取元素
    for i in range(n - 1, 0, -1):
        # 将堆顶元素(最大值)移到末尾
        arr[0], arr[i] = arr[i], arr[0]
        # 调整剩余元素为大顶堆
        heapify(arr, i, 0)
    
    return arr

def heapify(arr, n, i):
    """
    调整以 i 为根节点的子树为大顶堆
    :param arr: 数组
    :param n: 堆的大小
    :param i: 当前节点索引
    """
    largest = i  # 初始化最大值为根节点
    left = 2 * i + 1   # 左子节点
    right = 2 * i + 2  # 右子节点

    # 如果左子节点大于根节点
    if left < n and arr[left] > arr[largest]:
        largest = left

    # 如果右子节点大于当前最大值
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 如果最大值不是根节点，则交换并继续向下调整
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

# 测试用例
if __name__ == "__main__":
    data = [12, 11, 13, 5, 6, 7]
    print("原始数据:", data)
    print("排序结果:", heap_sort(data.copy()))

第四部分：归并与计数 —— 空间换时间与特殊场景

7. 归并排序 (Merge Sort)

算法思想基础：
典型的分治法应用。将数组递归地分成两半，分别排序，然后将两个有序的子数组合并成一个有序数组。

实现思路：

1. 分解：将数组从中间切开，递归排序左右两边。
2. 合并：准备两个指针分别指向左右子数组的开头，比较大小，将较小的放入新数组，直到其中一个子数组耗尽，再将另一个剩余部分追加到末尾。

具体实现代码：

文件名称：merge_sort.py

def merge_sort(arr):
    """
    归并排序
    时间复杂度: O(n log n), 空间复杂度: O(n)
    稳定排序
    """
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    # 递归分解
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    # 合并
    return merge(left, right)

def merge(left, right):
    """
    合并两个有序数组
    """
    result = []
    i = j = 0
    
    # 双指针比较
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # 添加剩余元素
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

# 测试用例
if __name__ == "__main__":
    data = [38, 27, 43, 3, 9, 82, 10]
    print("原始数据:", data)
    print("排序结果:", merge_sort(data.copy()))

8. 计数排序 (Counting Sort)

算法思想基础：
非比较型排序。统计每个值出现的次数，然后根据统计结果直接确定每个值在输出数组中的位置。适用于整数且范围不大的场景。

实现思路：

1. 找出数组中的最大值 max_val。
2. 创建一个长度为 max_val + 1 的计数数组 count。
3. 遍历原数组，统计每个数字出现的次数。
4. 对计数数组做累加处理（可选，用于处理稳定性或直接填充）。
5. 反向遍历原数组（保证稳定性），根据计数数组将元素放入结果数组。

具体实现代码：

文件名称：counting_sort.py

def counting_sort(arr):
    """
    计数排序
    时间复杂度: O(n + k), k为数据范围
    空间复杂度: O(k)
    仅适用于非负整数
    """
    if not arr:
        return arr
    
    max_val = max(arr)
    min_val = min(arr)
    range_size = max_val - min_val + 1
    
    # 计数数组
    count = [0] * range_size
    output = [0] * len(arr)
    
    # 统计频率
    for num in arr:
        count[num - min_val] += 1
    
    # 累加计数 (为了确定位置)
    for i in range(1, range_size):
        count[i] += count[i - 1]
    
    # 构建输出数组 (反向遍历保证稳定性)
    for num in reversed(arr):
        index = count[num - min_val] - 1
        output[index] = num
        count[num - min_val] -= 1
    
    return output

# 测试用例
if __name__ == "__main__":
    data = [4, 2, 2, 8, 3, 3, 1]
    print("原始数据:", data)
    print("排序结果:", counting_sort(data.copy()))

第五部分：其他经典排序

9. 桶排序 (Bucket Sort)

算法思想基础：
将数据分到有限数量的桶里，每个桶再分别排序（可以使用其他排序算法或递归使用桶排序）。适用于数据分布均匀的情况。

具体实现代码：

文件名称：bucket_sort.py

def bucket_sort(arr):
    """
    桶排序
    适用于数据分布均匀的场景
    """
    if not arr:
        return arr
    
    max_val = max(arr)
    min_val = min(arr)
    bucket_range = (max_val - min_val) / len(arr) if len(arr) > 1 else 1
    
    # 创建桶
    buckets = [[] for _ in range(len(arr) + 1)]
    
    # 分配数据到桶
    for num in arr:
        index = int((num - min_val) / bucket_range)
        # 处理边界情况，防止索引越界
        if index == len(buckets):
            index -= 1
        buckets[index].append(num)
    
    # 对每个桶排序并合并
    result = []
    for bucket in buckets:
        # 这里使用内置排序，也可以递归调用桶排序或其他排序
        result.extend(sorted(bucket))
    
    return result

# 测试用例
if __name__ == "__main__":
    data = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
    # 注意：上面的逻辑主要针对整数优化，浮点数需调整映射逻辑
    # 此处演示整数版本逻辑适配
    data_int = [42, 32, 33, 52, 37, 47, 51]
    print("原始数据:", data_int)
    print("排序结果:", bucket_sort(data_int.copy()))

10. 基数排序 (Radix Sort)

算法思想基础：
按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。通常配合计数排序作为子过程。

具体实现代码：

文件名称：radix_sort.py

def radix_sort(arr):
    """
    基数排序 (LSD - 最低位优先)
    适用于整数
    """
    if not arr:
        return arr
    
    max_val = max(arr)
    exp = 1  # 位数因子 1, 10, 100...
    
    while max_val // exp > 0:
        counting_sort_by_digit(arr, exp)
        exp *= 10
    
    return arr

def counting_sort_by_digit(arr, exp):
    """
    基于指定位数的计数排序辅助函数
    """
    n = len(arr)
    output = [0] * n
    count = [0] * 10  # 0-9
    
    # 统计当前位数的频率
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1
    
    # 累加
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    # 构建输出 (反向遍历保证稳定性)
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
    
    # 复制回原数组
    for i in range(n):
        arr[i] = output[i]

# 测试用例
if __name__ == "__main__":
    data = [170, 45, 75, 90, 802, 24, 2, 66]
    print("原始数据:", data)
    print("排序结果:", radix_sort(data.copy()))

算法演练：综合对比

为了更直观地理解各算法的性能差异，我们可以在本地运行以下测试脚本，对比不同规模数据下的耗时（此处仅为逻辑展示，实际运行需在本地环境）。

(注：n为数据量，k为数据范围，d为位数)

小结

从简单的冒泡排序到高效的堆排序，再到非比较类的计数排序，每一种算法都有其独特的设计哲学和适用场景。

• 初学者应重点掌握冒泡、选择和插入排序，理解排序的基本操作。
• 进阶者需深入理解快速排序的分治思想和堆排序的堆结构维护，这是面试的高频考点。
• 资深开发者则应根据数据特征（如数据量、分布、是否整数等）灵活选择计数、桶或基数排序，以达到极致的性能优化。

算法的学习不仅仅是记忆代码，更是思维方式的训练。希望本文提供的代码和分析能成为你手中的利剑，助你在编程世界中披荆斩棘。