算法如老友，常忆常新； 代码似陈酿，越写越香。

在Python的世界里，重温那些经典算法，不仅能巩固编程核心思想，更能让你在语言特性的运用上豁然开朗。

无论你已经是一位Python老手，还是仍在成长中的开发者，时常回头看看这些经典实现：

1、发现同一问题的多种Python式解法，领悟语言精髓

2、掌握如何利用Python特性让算法代码更简洁、高效

3、深入理解数据结构与Python内置类型的巧妙结合

4、从算法层面优化程序，提升代码性能与可读性

今天，就让我们带着对Python的理解，重新审视这些经典算法，开启一段温故知新的编程之旅！

1. 快速排序算法

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]
print("快速排序结果:", quick_sort(arr))

2. 二分查找算法

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


# 示例
sorted_arr = [1, 3, 5, 7, 9, 11, 13]
print("二分查找结果:", binary_search(sorted_arr, 9))

3. 斐波那契数列（动态规划版）

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]


# 示例
print("斐波那契数列第10项:", fibonacci(10))

4. Dijkstra最短路径算法

import heapq


def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    pq = [(0, start)]


    while pq:
        current_distance, current_node = heapq.heappop(pq)


        if current_distance > distances[current_node]:
            continue


        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight


            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))


    return distances


# 示例
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
print("Dijkstra算法结果:", dijkstra(graph, 'A'))

5. 字符串匹配算法（KMP）

def kmp_search(text, pattern):
    def build_lps(pattern):
        lps = [0] * len(pattern)
        length = 0
        i = 1


        while i < len(pattern):
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length-1]
                else:
                    lps[i] = 0
                    i += 1
        return lps


    lps = build_lps(pattern)
    i = j = 0
    result = []


    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1


            if j == len(pattern):
                result.append(i - j)
                j = lps[j-1]
        else:
            if j != 0:
                j = lps[j-1]
            else:
                i += 1


    return result


# 示例
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print("KMP算法匹配位置:", kmp_search(text, pattern))

6. 最长公共子序列（LCS）

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]


    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])


    # 回溯找出最长公共子序列
    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if text1[i-1] == text2[j-1]:
            result.append(text1[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1


    return ''.join(reversed(result))


# 示例
text1 = "ABCBDAB"
text2 = "BDCAB"
print("最长公共子序列:", longest_common_subsequence(text1, text2))

这些算法涵盖了排序、搜索、动态规划、图论等多个重要领域，掌握它们将对你的编程能力有很大提升！

小提示：在实际应用中，很多算法Python标准库已经提供了优化实现（如sorted()使用Timsort），但了解底层原理仍然非常重要。