Python 算法

算法不仅仅是计算思维。它是一个分步过程，指定一系列指令，按特定顺序执行以获得预期结果。简单来说，算法是为解决特定问题而设计的任何代码。我们可以用多种编程语言编写同一个算法，因为算法的构建通常与支持语言无关。

在本文中，我们将深入探讨 Python 算法的世界。本文将为您提供理解和实现算法的坚实基础。

什么是算法？

算法是一系列有限的代码，旨在按定义的顺序执行以解决问题并产生期望的输出。算法通常用通用语言（伪代码）编写，然后用任何编程语言实现。建议在纸上写下算法的伪代码，并在实现前使用一些测试用例进行测试。

编写高效算法的步骤

• 理解问题 - 在编写算法之前，请分析需求、约束条件以及期望的输入和输出。
• 选择合适的数据结构 - 选择合适的数据结构来设计高效的算法非常重要。
• 分析时间和空间复杂度 - 针对您的问题，争取找到具有最佳可能时间和空间复杂度的算法。
• 设计和测试算法 - 根据您对问题的理解，使用伪代码或流程图设计算法，并用各种输入对其进行彻底测试。
• 优化算法并再次测试 - 寻找潜在的优化点，并减少冗余计算和不必要的步骤。
• 记录算法 - 最后，记录算法，并提供其逻辑、输入、输出、空间和时间复杂度的清晰解释。

现在，让我们继续研究查找算法。

搜索算法

查找算法用于在数据序列中查找特定元素或值。

让我们探讨两种流行的查找算法：线性查找和二分查找。

1. 二分查找

• 二分查找算法基于分治原则。它用于在已排序的数据序列中查找值。
• 它通过将中间元素与目标值进行比较来重复将空间分成两半。
• 如果目标值大于中间值，则在子数组的右半部分进行搜索。如果目标值小于中间值，则在子数组的左半部分进行搜索。

编写二分查找算法的步骤

1. 计算中间索引，mid = (end - start + 1) // 2
2. 将中间元素与 x 进行比较。
3. 如果 x == arr[mid]，我们返回中间元素的索引。
4. 如果 x > arr[mid]，表示目标值 x 只能在子数组的右半部分（元素较大的部分）找到。然后，该方法会迭代或递归地再次用于右侧。
5. 否则，目标值 x 必须在子数组的左半部分（元素较小的部分）找到。然后，该方法用于左侧。

本文清楚地解释了二分查找的工作原理 -> 二分查找

代码：下面提供了二分查找的迭代实现

输出

Array = [5, 8, 16, 37, 59, 80]
The given element 59 is present at the index 4
The given element 35 is not present in the array

2. 线性查找

• 线性查找是最简单的查找算法，通常用于数据未排序或搜索空间较小时。
• 它依次检查数据结构中的每个元素，直到找到匹配项或未找到匹配项。

编写线性查找算法的步骤

• 使用 for 循环或 while 循环依次检查数组中的每个元素。
• 如果找到 x，则返回索引。
• 否则，返回 -1，表示 x 不在数组中。

本文清楚地解释了线性查找的工作原理 -> 线性查找

代码：线性查找的 Python 实现

输出

Array = [5, 8, 16, 37, 59, 80]
The given element 59 is present at the index 4
The given element 35 is not present in the array

现在，让我们深入了解 Python 排序算法的世界。

排序算法

排序算法以特定顺序（例如升序或降序）排列元素。我们将讨论一些基本排序算法：插入排序、冒泡排序、选择排序、归并排序和快速排序。

1. 插入排序

• 插入排序是一种简单的排序算法，其工作方式类似于我们整理扑克牌的方式。
• 它遍历列表的未排序部分，并将每个元素插入到已排序部分的正确位置。

编写插入排序算法的步骤

def insertion_sort(arr, n)

• 假定 arr[0] 已排序
• 从 i = 1 到 n-1 开始 for 循环
• key = arr[i]
• 将 key 与左侧已排序子数组中的每个元素进行比较
• 如果元素大于 key，则将其向右移动
• 将 key 插入到左侧子数组中的正确位置。

本文清楚地解释了插入排序的工作原理 -> 插入排序

代码：插入排序的 Python 实现

输出

Unsorted array: [23, 42, 3, 83, 36, 49, 19]
Sorted array: [3, 19, 23, 36, 42, 49, 83]

2. 选择排序

• 选择排序是一种简单的基于比较的排序算法。它将输入分为两部分：开头是已排序部分，结尾是未排序部分。
• 选择排序技术通过不断地从未排序部分选择最小的元素，并将其与已排序部分的当前位置元素交换，来对任何给定数组进行排序。

编写选择排序算法的步骤

def selection_sort(arr, n)

• 遍历数组中的每个元素 i = 0 到 n-2
• 从 i = i+1 到 n-1 开始 for 循环
• 从右侧子数组中选择最小的元素
• 将最小元素与右侧子数组（未排序部分）的第一个元素交换
• 重复这些步骤，直到所有元素都排序完毕

代码：选择排序的 Python 实现

输出

The sorted array is: [3, 19, 23, 36, 42, 49, 83]

3. 冒泡排序

冒泡排序是最简单也是效率最低的排序算法。它不断地比较相邻的元素，如果它们的顺序错误，则交换它们，从而逐渐将最大的元素移到列表的末尾。

编写冒泡排序算法的步骤

def bubble_sort(arr, n)

• 使用 for 循环遍历从 i = 0 到倒数第二个元素的每个元素
• 从 j = 0 到 len(arr)-i-1 开始另一个 for 循环
• 比较 arr[j] 和 arr[j+1] - 如果它们的顺序错误，则交换两者
• 重复此过程，直到所有元素都排序完毕

代码：冒泡排序的 Python 实现

输出

The sorted array is: [3, 19, 23, 36, 42, 49, 83]

4. 归并排序

• 归并排序是一种分治排序算法。它递归地将输入数组分成两半，独立地对每个半部分进行排序，然后将它们合并在一起。
• 它通过比较两个已排序半部分中的元素，并将它们以正确的顺序组合起来。

编写归并排序算法的步骤

def merge_sort(arr, n, left, right)

• 定义基本情况 - 如果 size(arr) = 1 则返回数组 # 数组中的单个元素始终已排序。
• 计算数组的中间值，并将其分成两半
• 对左子数组和右子数组再次调用归并排序
• 调用 Merge(arr, left, mid, right) 函数

def merge(arr, left, mid, right)

• 创建 arr1 = arr[left, mid] 和 arr2 = arr[mid+1, right] 的两个副本
• 比较两个新创建的子数组的元素
• 以正确的顺序将元素插入数组。
• 检查 arr1 或 arr2 中是否还有剩余元素
• 重复此任务，直到所有元素都插回主数组

代码：归并排序的 Python 实现

输出

The given array is: [23, 42, 3, 83, 36, 49, 19]
The sorted array is: [3, 19, 23, 36, 42, 49, 83]

5. 快速排序

• 快速排序也基于分治原则，与归并排序一样。
• 快速排序是一种高效的排序算法。
• 它根据选定的枢轴元素递归地将数组划分为更小的子数组，然后独立地对子数组进行排序。

编写快速排序算法的步骤

def quick_sort(arr, low, high)

• 划分数组并获取枢轴索引 - pivot_index = partition(arr, low, high)
• 递归地对左侧和右侧子数组进行排序
  • quick_sort(arr, low, pivot_index - 1)
  • quick_sort(arr, pivot_index + 1, high)

def partition(arr, low, high)

• 选择最右边的元素作为枢轴 - pivot = arr[high]
• 将枢轴索引初始化为最低索引 - pivot_index = low
• 选择所有小于枢轴的元素，并通过 for 循环将它们移到左侧。
• 将枢轴放置在数组中的正确位置。
• 将 pivot_index 返回给 quick_sort 函数。

代码：快速排序的 Python 实现

输出

The unsorted array is: [23, 42, 3, 83, 36, 49, 19]
The sorted array is: [3, 19, 23, 36, 42, 49, 83]

结论

在本文中，我们介绍了 Python 中的两种查找算法（线性查找和二分查找）以及五种排序算法（冒泡排序、插入排序、选择排序、归并排序和快速排序）。这些算法将帮助您编写高效的代码，并为您解决问题提供坚实的基础。