排序算法

冒泡排序（Bubble Sort）

原理：反复比较相邻两个元素，若顺序错误则交换。每一轮将未排序部分的最大值"冒泡"到末尾。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False  # 提前终止优化
        for j in range(0, n - i - 1):  # 每轮缩短一位
            if arr[j] > arr[j + 1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:    # 本轮无交换，数组已有序
            break
    return arr

最坏/平均时间O(n²) 最好（已排序）O(n) 空间O(1)

稳定性：稳定（相等元素不会交换位置）。实际很少使用，但概念简单。

选择排序（Selection Sort）

原理：每轮从未排序部分找到最小值，与未排序部分的第一个元素交换。

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]  # 交换最小值到最前
    return arr

所有情况O(n²) 空间O(1)

稳定性：不稳定（交换操作可能打乱相等元素的相对顺序）。比较次数固定为 n(n-1)/2，但交换次数最多 n-1 次，适合交换代价高的场景。

插入排序（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

最坏（逆序）O(n²) 最好（近有序）O(n) 空间O(1)

稳定性：稳定。小数据量或近乎有序时性能极好，是 TimSort 的核心组件。

归并排序（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

所有情况O(n log n) 空间O(n)

稳定性：稳定。需要 O(n) 辅助空间。适合链表排序（不需要随机访问）和外部排序（数据量超出内存）。

快速排序（Quick Sort）

原理：选取一个"基准值"（pivot），将数组分为"小于 pivot"和"大于 pivot"两部分，递归排序。

import random

def quick_sort(arr, low=0, high=None):
    if high is None: high = len(arr) - 1
    if low >= high: return
    pivot_idx = partition(arr, low, high)
    quick_sort(arr, low, pivot_idx - 1)
    quick_sort(arr, pivot_idx + 1, high)

def partition(arr, low, high):
    # 随机选 pivot，避免已排序数组退化为 O(n²)
    rand_idx = random.randint(low, high)
    arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
    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   # pivot 的最终位置

平均O(n log n) 最坏（退化）O(n²) 平均空间O(log n)

稳定性：不稳定。实践中速度最快（缓存友好），是多数标准库的首选。

堆排序（Heap Sort）

原理：先建最大堆，然后反复将堆顶（最大值）与末尾元素交换，再重新堆化，直到排序完成。

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[0], arr[i] = arr[i], arr[0]   # 堆顶↔末尾
        _heapify(arr, i, 0)               # 对缩小后的堆重建
    return arr

def _heapify(arr, n, i):
    largest = i
    l, r = 2*i+1, 2*i+2
    if l < n and arr[l] > arr[largest]: largest = l
    if r < n and arr[r] > arr[largest]: largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        _heapify(arr, n, largest)

所有情况O(n log n) 空间O(1)

稳定性：不稳定。原地算法，但缓存性能差，实践中比快排慢。

计数排序（Counting Sort）

原理：统计每个值出现的次数，然后按顺序重建数组。不基于比较，突破 O(n log n) 下界。

def counting_sort(arr, max_val=None):
    if not arr: return arr
    if max_val is None: max_val = max(arr)
    count = [0] * (max_val + 1)
    for x in arr:
        count[x] += 1           # 统计频次
    # 累加计数，转为"不超过 i 的元素有几个"
    for i in range(1, len(count)):
        count[i] += count[i-1]
    # 从右向左填入输出数组（保证稳定性）
    output = [0] * len(arr)
    for x in reversed(arr):
        count[x] -= 1
        output[count[x]] = x
    return output

时间O(n + k) 空间O(n + k)

k 为数值范围。稳定。适用于整数范围不大（k 不超过 O(n)）的场景，如年龄、分数排序。

基数排序（Radix Sort）

原理：按照数字的每一位（个位、十位、百位…）分别用计数排序，从最低位到最高位。

def radix_sort(arr):
    if not arr: return arr
    max_val = max(arr)
    exp = 1  # 当前处理的位（1=个位，10=十位...）
    while max_val // exp > 0:
        arr = _counting_by_digit(arr, exp)
        exp *= 10
    return arr

def _counting_by_digit(arr, exp):
    count = [0] * 10
    for x in arr:
        digit = (x // exp) % 10
        count[digit] += 1
    for i in range(1, 10):
        count[i] += count[i-1]
    output = [0] * len(arr)
    for x in reversed(arr):
        digit = (x // exp) % 10
        count[digit] -= 1
        output[count[digit]] = x
    return output

时间O(d · (n+k)) 空间O(n + k)

d 为最大数的位数，k 为基数（十进制 k=10）。稳定。适合整数排序。

对比总览

算法	最好	平均	最坏	空间	稳定	场景
冒泡	O(n)	O(n²)	O(n²)	O(1)	是	教学，几乎不用
选择	O(n²)	O(n²)	O(n²)	O(1)	否	交换代价高时
插入	O(n)	O(n²)	O(n²)	O(1)	是	小/近乎有序数组
归并	O(n log n)	O(n log n)	O(n log n)	O(n)	是	链表、稳定排序
快速	O(n log n)	O(n log n)	O(n²)	O(log n)	否	通用，实践最快
堆排	O(n log n)	O(n log n)	O(n log n)	O(1)	否	Top-K，严格空间
计数	O(n+k)	O(n+k)	O(n+k)	O(n+k)	是	小范围整数
基数	O(dn)	O(dn)	O(dn)	O(n+k)	是	多位整数/字符串