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

排序算法是计算机科学中最基础的内容之一，也是面试中的常客。Python 凭借其简洁的语法，成为学习和实现排序算法的绝佳语言。本文整理了多种经典排序算法的 Python 实现，包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序和基数排序，并附有详细注释和示例，帮助你理解每一种算法的核心思想与实现细节。

一、冒泡排序（Bubble Sort）

冒泡排序通过重复遍历待排序序列，比较相邻元素并交换顺序错误的元素，每一轮将最大（或最小）的元素“冒泡”到末尾。

基础版

def bubble_sort(collection):
    length = len(collection)
    for i in range(length - 1):
        for j in range(length - 1 - i):
            if collection[j] > collection[j + 1]:
                collection[j], collection[j + 1] = collection[j + 1], collection[j]
    return collection

优化版（加入交换标志）

def bubble_sort2(collection):
    length = len(collection)
    for i in range(length - 1):
        swapped = False
        for j in range(length - 1 - i):
            if collection[j] > collection[j + 1]:
                collection[j], collection[j + 1] = collection[j + 1], collection[j]
                swapped = True
        if not swapped:
            break
    return collection

二、选择排序（Selection Sort）

每次从待排序序列中选出最小（或最大）的元素，放到已排序序列的末尾。

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

三、插入排序（Insertion Sort）

将未排序序列中的元素逐个插入到已排序序列的合适位置。

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

四、希尔排序（Shell Sort）

希尔排序是插入排序的改进版，通过设置间隔（gap）将序列分组，对每组进行插入排序，逐步缩小间隔。

def shell_sort(arr):
    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

五、归并排序（Merge Sort）

采用分治法，将序列递归拆分为子序列，排序后再合并。

def merge_sort(arr):
    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

六、快速排序（Quick Sort）

选择一个基准元素，将序列分为小于基准和大于基准两部分，递归排序。

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

七、堆排序（Heap Sort）

利用堆这种数据结构进行排序，分为建堆和调整堆两个阶段。

def heapify(arr, n, 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)

def heap_sort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    return arr

八、基数排序（Radix Sort）

按照低位到高位的顺序，对每一位进行稳定排序（通常使用计数排序）。

def radix_sort(arr):
    max_num = max(arr)
    exp = 1
    while max_num // exp > 0:
        buckets = [[] for _ in range(10)]
        for num in arr:
            radix = (num // exp) % 10
            buckets[radix].append(num)
        i = 0
        for bucket in buckets:
            for num in bucket:
                arr[i] = num
                i += 1
        exp *= 10
    return arr

📌 总结