博客

Python实现七个基本算法的实例代码

  • Post category:Python

下面是关于“Python实现七个基本算法的实例代码”的完整攻略。

1. 七个基本算法

七个基本算法是指排序、查找、字符串、数组、表、树和图这七个领域的基本算法。这些算法是计算机科学中最基本的算法之一，也是Python开发者必须握的算法之一。

2. 算法实现

下面是使用Python实现七个基本算法的完整代码。

2.1 排序算法

2.1.1 冒泡排序

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        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

2.1.2 快速排序

def quick_sort(arr):
    if(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)

2.2 查找算法

2.2.1 二分查找

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

2.3 字符串算法

2.3.1 字符串反转

def reverse_string(s):
    return s[::-1]

2.4 数组算法

2.4.1 数组求和

def array_sum(arr):
    return sum(arr)

2.5 链表算法

2.5.1 链表反转

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

2.6 树算法

2.6.1 二叉树遍历

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder_traversal(root):
    if not root:
        return []
    return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)

2.7 图算法

2.7.1 图遍历

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(graph[vertex] - visited)
    return visited

3. 示例

下面是两个基本算法的示例，分别展示了冒泡排序和二分查找的实现。

3.1 冒排序示例

arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("Sorted array:", sorted_arr)

输出：

Sorted array: [11, 12, 22, 25, 34, 64, 90]

3.2 二分查找示例

arr = [2, 3, 4, 10, 40]
x = 10
result = binary_search(arr, x)
if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in array")

输出：

Element is present at index 3

4. 总结

七个基本算法是计算机科学中最基本的算法之一，也是Python开发者必掌握的算法之一。在Python中，我们可以使用各种数据结构和算法来实现这些基本算法。在实际应用中，我们可以根据具体问题选择适当的算法来进行开发和实现。

Tags: ,