当前位置:   article > 正文

python中常用的算法_python算法都有哪些

python算法都有哪些

Python中常用的算法有很多,这里我为你介绍几个常见的算法及其用法:

1,冒泡排序(Bubble Sort)

冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

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]

arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("排序后的数组:", arr)

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

2,二分查找(Binary Search)

二分查找是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。

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

arr = [2, 3, 4, 10, 40]
x = 10
result = binary_search(arr, x)
if result != -1:
    print("元素在数组中的索引为", result)
else:
    print("元素不在数组中")

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

3,快速排序(Quick Sort)

快速排序是一种分治法(Divide and Conquer)的排序算法,它的基本思想是:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后分别对这两部分记录继续进行排序,以达到整个序列有序。

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("原始数组:", arr)
arr = quick_sort(arr)
print("排序后的数组:", arr)

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

4,插入排序

插入排序是一种简单且易于理解的排序算法。它的基本思想是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

下面是Python中实现插入排序的步骤:

  1. 首先,我们将数组的第一个元素视为已排序的元素,即只包含一个元素的数组自然是排序好的。

  2. 然后,我们从第二个元素开始,将其与前面的元素比较。如果前面的元素比当前元素大,我们就将前面的元素向后移动一位,为当前元素腾出空间。

  3. 重复上述过程,直到当前元素找到合适的位置,即找到一个元素比它小或者已经遍历完所有元素。然后,我们将当前元素插入到这个位置。

  4. 重复上述过程,直到所有的元素都被排序。

下面是Python代码实现插入排序的例子:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >=0 and key < arr[j] :
                arr[j+1] = arr[j]
                j -= 1
        arr[j+1] = key
    return arr

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

在这段代码中,我们首先设定一个范围,从1到数组的长度。然后,我们将当前元素(key)与它前面的元素进行比较。如果前面的元素比当前元素大,我们就将前面的元素向后移动一位。最后,我们将当前元素插入到找到的位置。这个过程会一直重复,直到所有的元素都被排序。

5,二叉树

二叉树是一种特殊的数据结构,它是由节点组成的层次结构。在二叉树中,每个节点最多有两个孩子节点,通常被称为左孩子和右孩子。

在Python中,我们通常使用类来表示二叉树。下面是一个简单的二叉树实现:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

在这个例子中,我们定义了一个Node类,用于表示二叉树的节点。每个节点包含一个数据(data),以及指向左孩子(left)和右孩子(right)的引用。

然后,我们定义了一个BinaryTree类,它有一个根节点(root)。

我们可以使用这个二叉树进行各种操作,比如插入新的节点、查找节点、删除节点等。例如,我们可以添加一个方法来插入新的节点:

class BinaryTree:
    # ...
    def insert(self, data):
        if self.root is None:
            self.root = Node(data)
        else:
            self._insert(data, self.root)

    def _insert(self, data, node):
        if data < node.data:
            if node.left is None:
                node.left = Node(data)
            else:
                self._insert(data, node.left)
        else:
            if node.right is None:
                node.right = Node(data)
            else:
                self._insert(data, node.right)

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

在这个例子中,insert方法用于在二叉树中插入新的节点。如果根节点为空(即二叉树为空),则创建一个新的节点并设置为根节点。否则,我们调用一个辅助方法_insert,该方法会递归地将新的节点插入到正确的位置。

这只是二叉树在Python中的基本用法。实际上,二叉树有许多其他的应用,比如排序算法(如二叉搜索树)、图算法(如最小生成树)、动态规划等。


分形二叉树,是体现递归算法的经典案例。请你使用turtle库和递归算法绘制出如下图所示图形。

下面我将简单介绍一下如何使用Python的turtle库和递归算法来绘制分形二叉树。

首先,我们需要导入turtle库,并设置一些基本参数,如画笔速度、颜色等。然后,我们定义一个绘制分形二叉树的函数,该函数接受两个参数:分支长度和画笔。在函数中,我们首先判断分支长度是否大于某个阈值,如果大于阈值,则继续绘制左右两个子分支;否则,直接返回。在绘制子分支时,我们需要递归调用该函数,传入不同的分支长度和角度。最后,我们调用这个函数并启动turtle的事件循环。

下面是具体的代码实现:

import turtle

def draw_fractal_tree(branch_length, t):
    if branch_length > 5:
        t.forward(branch_length)
        t.right(20)
        draw_fractal_tree(branch_length - 15, t)
        t.left(40)
        draw_fractal_tree(branch_length - 15, t)
        t.right(20)
        t.backward(branch_length)

def main():
    t = turtle.Turtle()
    win = turtle.Screen()
    t.left(90)
    t.up()
    t.backward(100)
    t.down()
    t.color("green")
    draw_fractal_tree(75, t)
    win.exitonclick()

if __name__ == "__main__":
    main()

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

运行这段代码,你将看到一个美丽的分形二叉树图案。通过调整分支长度和角度等参数,你可以创建出不同形状的分形二叉树。
在这里插入图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/weixin_40725706/article/detail/746238
推荐阅读
相关标签
  

闽ICP备14008679号