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
测试冒泡排序
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("Sorted array is:", sorted_arr)

2. 快速排序算法

快速排序是一种分而治之的排序算法，通过选择一个“基准”元素，然后将数组分为两部分，一部分包含所有小于基准的元素，另一部分包含所有大于基准的元素。

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 array is:", sorted_arr)

3. 欧几里得算法求最大公约数

欧几里得算法是一种求两个正整数最大公约数（GCD）的算法，它基于这样的原理：两个整数的最大公约数等于其中较小数和两数的差的最大公约数。

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
测试欧几里得算法
print("GCD of 56 and 98 is:", gcd(56, 98))

4. 斐波那契数列

斐波那契数列是一个每一项都是前两项和的数列，通常形式为：0, 1, 1, 2, 3, 5, 8, 13, ...

def fibonacci(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a
测试斐波那契数列
print("Fibonacci of 10 is:", fibonacci(10))

5. 二分查找算法

二分查找是一种在有序数组中查找特定元素的搜索算法，它通过比较中间元素和目标值来缩小搜索范围。

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("Element is present at index", result)
else:
    print("Element is not present in array")

这些小程序展示了Python在实现经典算法方面的能力，同时也可以帮助初学者更好地理解和掌握这些算法。