排序算法

算法教程 · 第 3 章 · 6 次浏览

排序是算法的基本功。理解几种核心排序的思路和复杂度，比背代码重要。

常见排序

冒泡：相邻比较交换，O(n²)，简单教学用
选择：每轮选最小放前面，O(n²)
插入：像理扑克牌，小数据快，O(n²)
归并：分治，稳定，O(nlogn)
快排：分治 + 基准，平均 O(nlogn)，工程最常用

工程实践

Python 的 sorted() 是 Timsort（混合排序），直接用它，别自己写排序。

代码示例

# 冒泡排序 O(n²)
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(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

# 快排 O(nlogn)
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + mid + quick_sort(right)

print(bubble_sort([5, 2, 8, 1, 9]))
print(quick_sort([5, 2, 8, 1, 9]))
print(sorted([5, 2, 8, 1, 9]))    # 工程直接用它

📚 Python 语法速查

常用条目速查，完整版见对应教程章节。可复制代码到在线运行中测试。

写法 / 语法	作用
`print("hello")`	输出到控制台
`name = "张三"`	变量赋值（无需声明类型）
`if x > 0: ...`	条件判断（注意冒号和缩进）
`for i in range(10): ...`	循环（缩进是语法的一部分）
`while x < 10: ...`	条件循环
`def fn(a, b): return a + b`	定义函数
`class Person: ...`	定义类
`list = [1, 2, 3]`	列表（可改）
`tuple = (1, 2)`	元组（不可改）
`dict = {"key": "value"}`	字典（键值对）
`set = {1, 2, 3}`	集合（去重）
`len(obj)`	取长度
`str(x) / int(x) / float(x)`	类型转换
`s.split(",")`	字符串按分隔符拆分
`" ".join(list)`	列表拼接成字符串
`import os`	导入模块
`from math import sqrt`	从模块导入指定函数
`try: ... except Exception as e: ...`	异常捕获
`with open("a.txt", "r") as f: ...`	文件读取（自动关闭）
`f"你好 {name}"`	f-string 格式化
`lambda x: x * 2`	匿名函数
`list(map(fn, arr))`	函数式处理列表
`range(start, stop, step)`	生成数字序列
`if __name__ == "__main__":`	主入口判断
`pip install 包名`	安装第三方包（命令行）