Python常用算法

Python常用算法包括排序、搜索、图算法、动态规划等。

Python常用算法

在计算机科学中，算法是解决问题的一系列步骤，Python作为一门广泛使用的编程语言，有许多常用的算法可以帮助我们解决各种问题，本文将介绍一些Python中常用的算法及其实现。

排序算法

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、选择排序

选择排序是一种简单直观的排序算法，它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

def selection_sort(arr):
    for i in range(len(arr)):
        min_index = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

查找算法

1、线性查找

线性查找是一种简单的查找算法，它的基本思想是从数列的第一个元素开始，逐个检查每个元素，直到找到所需的元素为止。

def linear_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

2、二分查找

二分查找是一种高效的查找算法，它要求数据必须是有序的，基本思想是将查找的键值与有序数组的中间值进行比较，如果相等则返回中间值的下标，如果小于中间值则在左半部分继续查找，如果大于中间值则在右半部分继续查找，直到找到为止。

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

图算法

1、深度优先搜索（DFS）

深度优先搜索是一种用于遍历或搜索树或图的算法，这个算法会尽可能深地搜索树的分支，当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点，这一过程一直进行到已发现从源节点可达的所有节点为止。

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

2、广度优先搜索（BFS）

广度优先搜索是一种用于遍历或搜索树或图的算法，这个算法从根节点开始，沿着树的宽度遍历树的节点，如果所有节点均被访问，则算法终止。

from collections import deque
def bfs(graph, root):
    visited = set()
    queue = deque([root])
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited)
    return visited

相关问题与解答

1、冒泡排序的时间复杂度是多少？

答：冒泡排序的时间复杂度为O(n^2)。

2、二分查找适用于什么样的数据结构？

答：二分查找适用于有序的数据结构，如有序数组。

3、深度优先搜索和广度优先搜索有什么区别？

答：深度优先搜索是尽可能深地搜索树的分支，而广度优先搜索是沿着树的宽度遍历树的节点。

4、选择排序的原理是什么？

答：选择排序的工作原理是在每一轮中选出最小的元素，然后将其放到正确的位置。