Python常用算法学习基础教程

本攻略将介绍Python常用算法的基础知识，包括排序算法、查找算法、递归算法等。我们将使用示例代码来演示这些算法的实现过程。

排序算法

冒泡排序

冒泡排序是一种简单的算法，它的基本思想是通过相邻元素之间的比较和交换来把小的元素逐步“冒泡”到数组的顶端。以下是示例代码，演示如何实现冒泡排序：

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("排序后的数组：")
for i in range(len(arr)):
    print(" %d" %arr[i])

在上面的示例代码中，我们定义了一个bubble_sort()函数来实现冒泡排序。然后，我们创建了一个包含7个元素的数组，并调用bubble_sort()函数对其进行排序。最后，我们输出了排序后的数组。

快速排序

快速排序是一种高效的排序算法，它的基本思想是通过分治法将一个大的数组分成两个小的数组，然后递归地对这两个小的数组进行排序。以下是示例代码，演示如何实现快速排序：

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi-1)
        quick_sort(arr, pi+1, high)

def partition(arr, low, high):
    i = low - 1
    pivot = arr[high]
    for j in range(low, high):
        if arr[j] <= pivot:
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i+1

arr = [64, 34, 25, 12, 22, 11, 90]
n = len(arr)
quick_sort(arr, 0, n-1)
print("排序后的数组：")
for i in range(n):
    print("%d" %arr[i])

在上面的示例代码中，我们定义了一个quick_sort()函数来实现快速排序。然后，我们创建了一个包含7个元素的数组，并调用quick_sort()函数对其进行排序。最后，我们输出了排序后的数组。

查找算法

二分查找

二分查找是一种高效的查找算法，它的基本思想是通过将有序数组分成两个部分，然后递归地在其中一个部分中查找目标元素。以下是示例代码，演示如何实现二分查找：

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

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

在上面的示例代码中，我们定义了一个binary_search()函数来实现二分查找。然后，我们创建了一个包含5个元素的有序数组，并用binary_search()函数查找目标元素。最后，我们输出了目标元素在数组中的索引。

递归算法

阶乘

阶乘是一种常见的递归算法，它的基本思想是将一个数分解成一个小于它的数和它本身的积，然后递归地计算这个小于它的数的阶乘。以下是示例代码，演示如何实现阶乘：

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

num = 5
print("%d 的阶乘为 %d" %(num, factorial(num)))

在上面的示例代码中，我们定义了一个factorial()函数来实现阶乘。然后，我们调用factorial()函数计算目标数的阶乘。最后，我们输出了目标数的阶乘。

总结

本攻略介绍了Python常用算法的基础知识，包括排序算法、查找算法、递归算法等。我们通过示例代码演示了这些算法的实现过程，并提供了一个阶乘的示例。需要根据具体的需求选择合适的算法。