Python 学习之路(十)--常见算法实现原理及解析
文章目录
- 1. **排序算法**
- (1) 冒泡排序(Bubble Sort)
- (2) 快速排序(Quick Sort)
- (3) 归并排序(Merge Sort)
- 2. **查找算法**
- (1) 线性查找(Linear Search)
- (2) 二分查找(Binary Search)
- 3. **图算法**
- (1) 深度优先搜索(DFS)
- (2) 广度优先搜索(BFS)
- 4. **动态规划算法**
- 背包问题(Knapsack Problem)
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)