青少年 Python 算法入门实战：排序、查找与递归

冒泡排序的思路特别朴素：从左到右，相邻两个数比一下，如果左边比右边大就交换。这样一轮走完，最大的数就像气泡一样"冒"到最右边。再来一轮，第二大的冒到倒数第二。重复 n 轮就排好了。

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

print(bubble_sort([5, 2, 9, 1, 5, 6]))

Python 里交换两个变量不用临时变量，直接 `arr[j], arr[j+1] = arr[j+1], arr[j]`，非常优雅。

冒泡排序的缺点是慢——n 个数要走 n 轮，每轮比 n 次，总共大约 n 的平方次比较。但它是理解排序思想最好的起点。

想象一本 1000 页的字典，要找"中"字在哪一页。最笨的方法是从第 1 页翻到第 1000 页。聪明的方法是：翻到中间第 500 页，看"中"在左边还是右边，把范围砍成 500 页。再翻到剩下一半的中间，再砍一半。

1000 页只要砍 10 次就能找到——这就是二分查找。前提是数据已经排好序。

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

print(binary_search([1, 3, 5, 7, 9, 11], 7))

对比一下：在 100 万个数里找一个数，顺序查找平均要 50 万次比较，二分查找只要 20 次。这就是算法的威力。

递归是算法里最神奇的思想：一个问题，如果能拆成"一个小一点的同类问题 + 一步简单操作"，那就可以让函数自己调用自己。

比如求 n 的阶乘：n! = n × (n-1)!。而 0! = 1。这就是一个递归定义。

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(5))

递归有两个关键：基线条件（什么时候停，这里是 n==0）和递归条件（怎么把问题变小，这里是 n-1）。没有基线条件，函数会无限调用自己直到栈溢出。

斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21……每一项等于前两项之和。用递归写只要三行：

def fib(n):
    if n <= 2:
        return 1
    return fib(n - 1) + fib(n - 2)

print(fib(10))

但是！这个写法有个大问题：算 fib(30) 会非常慢，因为它重复算了很多次。fib(5) 在不同分支里被算了成千上万次。这就是递归的经典坑——重复子问题。

改进方法：用循环或者加一个缓存（memoization）。这个改进思路，就是后面动态规划算法的入门。