10个经典Python入门算法代码:冒泡排序与斐波那契数列

纸上星河
纸上星河
发布时间:2026-11-18| 4人浏览过
原创

精选10个经典Python入门算法,深入讲解冒泡排序、斐波那契数列、二分查找等算法的执行机制、代码实现与复杂度分析。

学习编程算法的核心不是背诵代码,而是理解数据如何流转、状态如何转移。本文精选10个专为初学者设计的经典算法,以最具代表性的“冒泡排序”与“斐波那契数列”为轴心,提供可以直接在Python 3环境运行的完整源码、执行输出示例与机制拆解,帮助读者建立起清晰的算法思维。

1. 冒泡排序(Bubble Sort)

冒泡排序是所有排序算法的起点。它的基本逻辑是:重复遍历待排序数组,每次比较两个相邻元素,如果它们的顺序错误就交换位置。每一轮遍历结束后,当前序列中最大的元素都会“浮”到未排序部分的末端。

10个经典Python入门算法代码:冒泡排序与斐波那契数列
图 1: 冒泡排序单轮遍历的核心执行机制
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]:
                # Python特有的解包交换
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

# 测试用例
data = [64, 34, 25, 12, 22, 11, 90]
print("排序结果:", bubble_sort(data))
示例输出:排序结果: [11, 12, 22, 25, 34, 64, 90]

注意:内层循环边界必须写为 n - i - 1,因为末尾的 i 个元素已经排定,无需重复比较,减 1 则防止索引越界。

2. 斐波那契数列(Fibonacci Sequence)

斐波那契数列定义为:从第3项开始,每一项都等于前两项之和(0, 1, 1, 2, 3, 5, 8...)。很多初学者直接写递归,导致大量的重复运算;在实际编程中,使用线性迭代或记忆化是效率更高的方案。

10个经典Python入门算法代码:冒泡排序与斐波那契数列
图 2: 斐波那契数列朴素递归调用树与状态重叠示意
def fibonacci_iterative(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    
    # 状态转移:只需维护前两个数字
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

# 测试用例
print("第 10 项斐波那契数:", fibonacci_iterative(10))
示例输出:第 10 项斐波那契数: 55

3. 二分查找(Binary Search)

二分查找专门用于在已排序列表中查找目标。它每次取中间元素与目标值对比,若不匹配,则根据大小关系舍弃一半搜索区间。这体现了经典的“分治”思想。

def binary_search(arr, target):
    left = 0
    right = 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  # 未找到

# 测试用例 (列表必须有序)
sorted_list = [3, 9, 14, 19, 27, 33, 45, 52]
print("查找 27 的索引:", binary_search(sorted_list, 27))
示例输出:查找 27 的索引: 4

4. 选择排序(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
        # 将找到的最小值换到位置 i
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# 测试用例
print("选择排序结果:", selection_sort([29, 10, 14, 37, 13]))
示例输出:选择排序结果: [10, 13, 14, 29, 37]

5. 插入排序(Insertion Sort)

插入排序的逻辑就像整理手中的扑克牌。我们从左到右遍历列表,假设左侧部分始终有序,然后把当前取到的元素依次与左侧元素比较,为它找到合适的位置并插入进去。

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # 将大于 key 的元素向后移一位
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# 测试用例
print("插入排序结果:", insertion_sort([12, 11, 13, 5, 6]))
示例输出:插入排序结果: [5, 6, 11, 12, 13]

6. 线性查找(Linear Search)

线性查找是最原始也是最鲁棒的查找策略。在列表无序或者数据量极小的情况下,逐一比对元素是无需额外准备工作的标准方案。

def linear_search(arr, target):
    for index, value in enumerate(arr):
        if value == target:
            return index
    return -1

# 测试用例
raw_list = [4, 2, 9, 7, 1, 8]
print("查找 7 的索引:", linear_search(raw_list, 7))
示例输出:查找 7 的索引: 3

7. 欧几里得最大公约数算法(GCD)

辗转相除法(欧几里得算法)是数学与计算机结合的经典之作。它基于一条定理:两个正整数 a 和 b(a > b),它们的最大公约数等于 a 除以 b 的余数 r 和 b 之间的最大公约数。

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# 测试用例
print("48 和 18 的最大公约数:", gcd(48, 18))
示例输出:48 和 18 的最大公约数: 6

8. 双指针回文字符串检测(Palindrome Check)

回文字符串是指正读和反读都相同的文本。使用首尾双指针向中间靠拢检测,能够在常数额外空间下完成判定,是学习“双指针技巧”的极佳入口。

def is_palindrome(s):
    # 过滤非字母数字字符并转为小写
    cleaned = ''.join(ch.lower() for ch in s if ch.isalnum())
    left, right = 0, len(cleaned) - 1
    
    while left < right:
        if cleaned[left] != cleaned[right]:
            return False
        left += 1
        right -= 1
    return True

# 测试用例
print("是否为回文串:", is_palindrome("A man, a plan, a canal: Panama"))
示例输出:是否为回文串: True

9. 阶乘计算(Factorial: 迭代与递归)

阶乘(n!)即 1 到 n 之间所有正整数的乘积。它是理解递归基线条件(Base Case)与递推展开的基础模型。在生产中优先选择迭代方式以避免栈溢出。

def factorial(n):
    if n < 0:
        raise ValueError("负数没有阶乘")
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

# 测试用例
print("5 的阶乘:", factorial(5))
示例输出:5 的阶乘: 120

10. 两数之和(Two Sum 哈希查找)

两数之和通常作为各类数据结构面试的第一题。暴力的双层循环时间复杂度为 O(n²),而通过 Python 的字典(哈希表)记录访问过的数字与索引,可以将查找优化至线性时间复杂度 O(n)。

def two_sum(nums, target):
    lookup = {}
    for index, num in enumerate(nums):
        diff = target - num
        if diff in lookup:
            return [lookup[diff], index]
        lookup[num] = index
    return []

# 测试用例
print("目标和索引匹配结果:", two_sum([2, 7, 11, 15], 9))
示例输出:目标和索引匹配结果: [0, 1]

算法复杂度与核心逻辑对比

在工程实践中,评判一段算法的好坏主要依赖时间复杂度(耗时长短)和空间复杂度(消耗内存)。下表汇总了本文介绍的 10 个入门算法在平均情况下的资源消耗特征:

算法名称 平均时间复杂度 额外空间复杂度 核心设计思想
冒泡排序 O(n²) O(1) 相邻比较、极值沉底
斐波那契(迭代) O(n) O(1) 滚动变量、状态转移
二分查找 O(log n) O(1) 折半搜索、分治裁剪
选择排序 O(n²) O(1) 线性遍历找极小值
插入排序 O(n²) O(1) 局部有序维护、移位插入
线性查找 O(n) O(1) 逐项扫描、无序遍历
欧几里得 GCD O(log(min(a, b))) O(1) 辗转相除、模运算
回文检测 O(n) O(1) 首尾对齐、双指针逼近
阶乘计算(迭代) O(n) O(1) 乘法累积、边界终止
两数之和(哈希) O(n) O(n) 空间换时间、哈希寻址
10个经典Python入门算法代码:冒泡排序与斐波那契数列
图 3: 常见时间复杂度增长曲线对比

初学者的算法避坑指南与进阶路径

在动手敲这10个经典算法代码时,初学者经常会在索引边界、变量作用域和退出条件上踩坑。以下三项是最常见的注意点:

1. 索引边界越界(IndexError): 在写像冒泡排序、二分查找这样的算法时,arr[j + 1] 或者 right = len(arr) - 1 中的加减操作最容易导致索引超出数组长度。在下笔写循环前,先手工带入 n=0 和 n=1 验证边缘条件。
2. 区分原址修改与新对象生成: arr.sort() 是直接在原列表上修改(空间消耗小),而 sorted(arr) 会生成新列表。本文中的冒泡、选择与插入排序均属于原地算法(In-place Algorithm),不会创建额外列表。
10个经典Python入门算法代码:冒泡排序与斐波那契数列
图 4: 从基础模拟到高阶算法的进阶认知路径

掌握这10个基础代码后,建议脱离教程,尝试用白纸或空编辑器独立重写一遍“冒泡排序”与“斐波那契数列迭代版”。当你能不假思索地写出边界条件与状态更新语句时,算法底层的逻辑链条就已经在你的思维中建立完成了。

相关专题:

免责声明:本文内容仅供参考,不代表本站观点。转载或引用请注明出处。

Python 相关产品和应用

全部下载
Selenium

Selenium

4.51.0 · Windows

用于浏览器自动化和 Web 测试的 Python 工具。

scikit-learn

scikit-learn

1.9.1 · Windows

常用 Python 机器学习算法与模型评估工具库。

Black

Black

26.10.1 · Windows

强调一致性的 Python 自动代码格式化工具。

Ruff

Ruff

0.17.1 · macOS

由 Rust 编写的高速 Python 代码检查和格式化工具。

pytest

pytest

9.1.1 · Windows

简洁而强大的 Python 自动化测试框架。

FastAPI

FastAPI

0.146.0 · Windows

高性能 Python API 框架,支持类型提示和自动接口文档。

Flask

Flask

3.1.3 · Windows

轻量灵活的 Python Web 应用框架。

Django

Django

6.1.2 · Windows

成熟的 Python Web 框架,适合构建内容站点和业务系统。

Spyder

Spyder

6.1.7 · Windows

面向科学计算与数据分析的 Python 集成开发环境。

SciPy

SciPy

1.18.1 · Windows

面向科学、工程和技术计算的 Python 算法库。