Python 中常用的算法

1. 排序算法

用于将数据按特定顺序排列。

• 冒泡排序（Bubble Sort）
• 选择排序（Selection Sort）
• 插入排序（Insertion Sort）
• 快速排序（Quick Sort）
• 归并排序（Merge Sort）
• 堆排序（Heap Sort）
• 计数排序（Counting Sort）
• 基数排序（Radix Sort）
• 桶排序（Bucket Sort）

2. 搜索算法

用于在数据集中查找特定元素。

• 线性搜索（Linear Search）
• 二分搜索（Binary Search）
• 深度优先搜索（DFS, Depth-First Search）
• 广度优先搜索（BFS, Breadth-First Search）

3. 图算法

用于处理图结构数据。

• Dijkstra 算法（最短路径）
• Floyd-Warshall 算法（所有节点对的最短路径）
• Bellman-Ford 算法（带负权边的最短路径）
• Kruskal 算法（最小生成树）
• Prim 算法（最小生成树）
• 拓扑排序（Topological Sort）
• 强连通分量（Strongly Connected Components）

4. 动态规划

用于解决具有重叠子问题和最优子结构的问题。

• 斐波那契数列
• 背包问题（Knapsack Problem）
• 最长公共子序列（LCS, Longest Common Subsequence）
• 最长递增子序列（LIS, Longest Increasing Subsequence）
• 矩阵链乘法（Matrix Chain Multiplication）
• 编辑距离（Edit Distance）

5. 贪心算法

在每一步选择中采取当前最优的选择。

• 活动选择问题（Activity Selection Problem）
• 霍夫曼编码（Huffman Coding）
• 最小生成树（MST, Minimum Spanning Tree）
• 硬币找零问题（Coin Change Problem）

6. 分治算法

将问题分解为更小的子问题，分别解决后再合并结果。

• 归并排序（Merge Sort）
• 快速排序（Quick Sort）
• 二分搜索（Binary Search）
• 大整数乘法（Karatsuba Algorithm）

7. 回溯算法

通过试错的方式寻找问题的解，通常用于组合问题。

• 八皇后问题（N-Queens Problem）
• 数独求解（Sudoku Solver）
• 子集生成（Subset Generation）
• 排列组合（Permutations and Combinations）

8. 字符串算法

用于处理字符串相关的问题。

• KMP 算法（字符串匹配）
• Rabin-Karp 算法（字符串匹配）
• 最长回文子串（Longest Palindromic Substring）
• 字符串编辑距离（Edit Distance）
• Trie 树（前缀树）

9. 数学算法

用于解决数学问题。

• 欧几里得算法（最大公约数）
• 素数检测（Sieve of Eratosthenes）
• 快速幂算法（Exponentiation by Squaring）
• 斐波那契数列（Fibonacci Sequence）
• 牛顿迭代法（求平方根）

10. 机器学习算法

用于数据分析和预测。

• 线性回归（Linear Regression）
• 逻辑回归（Logistic Regression）
• K 近邻算法（K-Nearest Neighbors, KNN）
• 决策树（Decision Tree）
• 随机森林（Random Forest）
• 支持向量机（SVM, Support Vector Machine）
• K 均值聚类（K-Means Clustering）

11. 其他常用算法

• 哈希算法（Hash Functions）
• 滑动窗口算法（Sliding Window）
• 双指针算法（Two Pointers）
• 位运算算法（Bit Manipulation）

示例代码：快速排序（Quick Sort）

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = 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)

# 示例使用
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("排序后的数组:", sorted_arr)