Python 学习之路（十）--常见算法实现原理及解析

1. 排序算法

(1) 冒泡排序（Bubble Sort）

原理：
冒泡排序是一种简单的排序算法，它通过重复遍历列表，比较相邻的元素并交换它们的位置，直到整个列表有序为止。每一轮遍历会将最大的元素“冒泡”到列表末尾。

代码实现：

def bubble_sort(arr):n = len(arr)for i in range(n):# 每次遍历时，最后i个元素已排序完成，无需再比较for j in range(0, n - i - 1):if arr[j] > arr[j + 1]:arr[j], arr[j + 1] = arr[j + 1], arr[j]return arr

时间复杂度：

• 最坏情况：O(n²)（当列表完全逆序）
• 平均情况：O(n²)
• 最好情况：O(n)（如果列表已经有序，可以通过优化提前终止）

优化方法：
添加一个标志位，如果某一轮没有发生任何交换，说明列表已经有序，可以直接退出循环。

---

(2) 快速排序（Quick Sort）

原理：
快速排序是一种分治法（Divide and Conquer）的经典应用。它选择一个基准元素（pivot），将数组分为两个子数组：一部分小于基准值，另一部分大于基准值。然后对这两个子数组递归地进行快速排序。

代码实现：

def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]  # 选择中间元素作为基准left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right)

时间复杂度：

• 最坏情况：O(n²)（当每次划分极不平衡时）
• 平均情况：O(n log n)

优化方法：
随机选择基准值或三数取中法，避免最坏情况的发生。

---

(3) 归并排序（Merge Sort）

原理：
归并排序也是分治法的一种。它将数组分成两半，分别对两半进行排序，然后将排好序的两半合并成一个有序数组。

代码实现：

def merge_sort(arr):if len(arr) <= 1:return arrdef merge(left, right):result = []i = j = 0while i < len(left) and j < len(right):if left[i] < right[j]:result.append(left[i])i += 1else:result.append(right[j])j += 1result.extend(left[i:])result.extend(right[j:])return resultmid = len(arr) // 2left = merge_sort(arr[:mid])right = merge_sort(arr[mid:])return merge(left, right)

时间复杂度：

• 最坏情况：O(n log n)
• 平均情况：O(n log n)

优点：
稳定排序，适合链表结构等应用场景。

---

2. 查找算法

(1) 线性查找（Linear Search）

原理：
线性查找是最基本的查找方式，从头开始逐个检查元素，直到找到目标元素或遍历完整个列表。

代码实现：

def linear_search(arr, target):for i, val in enumerate(arr):if val == target:return ireturn -1

时间复杂度：

• 最坏情况：O(n)
• 平均情况：O(n)

适用场景：
无序列表或数据量较小的情况。

---

(2) 二分查找（Binary Search）

原理：
二分查找适用于有序列表。它通过不断缩小搜索范围，将目标值与中间元素比较，若目标值小于中间元素，则在左半部分继续查找；否则在右半部分查找。

代码实现：

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

时间复杂度：

• 最坏情况：O(log n)
• 平均情况：O(log n)

适用场景：
有序列表中的高效查找。

---

3. 图算法

(1) 深度优先搜索（DFS）

原理：
深度优先搜索是一种用于遍历或搜索树、图的算法。它沿着一条路径尽可能深入地探索，直到无法继续前进，然后回溯。

代码实现：

def dfs(graph, start, visited=None):if visited is None:visited = set()visited.add(start)print(start)for neighbor in graph[start]:if neighbor not in visited:dfs(graph, neighbor, visited)

时间复杂度：

• O(V + E)，其中 V 是顶点数，E 是边数。

---

(2) 广度优先搜索（BFS）

原理：
广度优先搜索按层遍历图，首先访问起始节点的所有邻居，然后再访问邻居的邻居，依此类推。

代码实现：

from collections import dequedef bfs(graph, start):visited = set()queue = deque([start])visited.add(start)while queue:node = queue.popleft()print(node)for neighbor in graph[node]:if neighbor not in visited:visited.add(neighbor)queue.append(neighbor)

时间复杂度：

• O(V + E)

---

4. 动态规划算法

背包问题（Knapsack Problem）

原理：
动态规划是一种解决复杂问题的方法，通常用于具有重叠子问题和最优子结构的问题。背包问题是经典的动态规划问题之一，目标是在容量限制下最大化物品价值。

代码实现：

def knapsack(weights, values, capacity):n = len(values)dp = [[0] * (capacity + 1) for _ in range(n + 1)]for i in range(1, n + 1):for w in range(capacity + 1):if weights[i - 1] <= w:dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w])else:dp[i][w] = dp[i - 1][w]return dp[n][capacity]

时间复杂度：

• O(n * capacity)