排序基础概念

What · 是什么

排序算法（sorting algorithm）是把一组数据按某种顺序（如升序/降序）排列的算法。本节点是排序主题的总览，重点掌握三件事：①稳定性（stable）概念——相等元素排序后相对顺序是否改变；②时间复杂度（尤其最坏情况）如何衡量；③比较排序（comparison sort）与非比较排序（non-comparison sort）的分类。基于比较的排序在最坏情况下存在 Ω(n log n) 的比较次数下界；而非比较排序（计数/桶/基数）利用键值的额外结构，可在 O(n+w) 等线性时间内完成。

Why · 为什么

How · 实现

伪代码

# 稳定性判定
对每个键值相等的元素对 (i<j, a[i]==a[j])，检查排序后 i 是否仍在 j 之前。

# 复杂度衡量
统计基本操作（比较/交换/赋值）次数随 n 增长的量级。

Python 实现

def is_stable_sort(sort_fn, arr):
    """检测排序算法是否稳定：对带索引的元素排序，检查相同键值是否保持相对顺序"""
    indexed = [(v, i) for i, v in enumerate(arr)]
    sort_fn(indexed, lambda x: x[0])
    # 相同值 v 的索引序列应严格递增才稳定
    by_val = {}
    for v, i in indexed:
        by_val.setdefault(v, []).append(i)
    return all(seq == sorted(seq) for seq in by_val.values())


def stable_demo():
    """用 Python 内建 sort（Timsort，稳定）演示"""
    arr = [(3, 'a'), (1, 'x'), (3, 'b'), (2, 'y')]
    arr.sort(key=lambda x: x[0])
    return arr


def complexity_table():
    """常用排序复杂度总览（最坏情况）"""
    table = [
        ("冒泡/选择/插入", "O(n^2)", "稳定/不稳定/稳定", "比较型"),
        ("归并排序", "O(n log n)", "稳定", "比较型"),
        ("快速排序", "O(n^2)（期望 O(n log n)）", "不稳定", "比较型"),
        ("堆排序", "O(n log n)", "不稳定", "比较型"),
        ("计数排序", "O(n+w)", "稳定", "非比较型"),
        ("基数排序", "O(d(n+k))", "稳定", "非比较型"),
        ("桶排序", "O(n)（均匀分布时）", "视内层排序而定", "非比较型"),
    ]
    return table


if __name__ == "__main__":
    assert is_stable_sort(lambda a, k: a.sort(key=k), [4, 1, 3, 4, 2, 1])
    print("稳定排序检测 OK")
    print("稳定排序演示:", stable_demo())
    for row in complexity_table():
        print("  ".join(row))

易错点

• 混淆『平均复杂度』与『最坏复杂度』：快排平均 O(n log n) 但最坏 O(n^2)，评测数据可构造卡死朴素实现
• 误以为计数排序也是基于比较：它利用键值范围，故可突破 n log n 下界
• 把稳定性当『性能』：稳定性只是相等元素的相对顺序属性，与速度无关

例题

信源

• OI Wiki✓ https://oi-wiki.org/basic/sort-intro/
• 书籍✓ CPH ch3 p35
• Wikipedia✓ https://zh.wikipedia.org/wiki/排序算法