本文档提供了TheAlgorithms/Python仓库中排序和搜索算法实现的详细信息。这些算法是基本计算过程，它们要么按特定顺序排列元素（排序），要么在集合中定位特定元素（搜索）。该仓库包含各种算法实现，每种算法都有不同的性能特征、策略和用例。
TheAlgorithms/Python仓库包含经典排序和搜索算法的实现。排序实现位于sorts/目录中，而搜索实现位于searches/目录中。所有实现都为处理可比较项的集合提供了统一的接口。
来源
搜索算法在集合中定位特定元素。该仓库实现了具有各种优化和接口的顺序搜索和二分搜索策略。
线性搜索顺序检查每个元素，直到找到目标或耗尽集合。该仓库提供了迭代和递归实现。
linear_search()函数在searches/linear_search.py12-33提供了直接的实现
rec_linear_search()函数在searches/linear_search.py36-65提供了递归方法
来源
二分搜索算法在已排序的集合上工作，重复地将搜索区间分成两半。该仓库提供了具有不同接口和优化的多个二分搜索实现。
searches/binary_search.py 模块实现了几种二分搜索变体
binary_search() searches/binary_search.py181-215 - 基本迭代实现binary_search_std_lib() searches/binary_search.py218-243 - 使用 Python 的bisect模块binary_search_by_recursion() searches/binary_search.py246-283 - 递归实现exponential_search() searches/binary_search.py286-322 - 指数搜索与二分搜索结合该仓库还提供了与 Python 的bisect模块相对应的二分法实用程序
bisect_left() searches/binary_search.py18-57 - 查找最左侧位置的插入点bisect_right() searches/binary_search.py60-98 - 查找最右侧位置的插入点insort_left() searches/binary_search.py101-138 - 将元素插入最左侧位置insort_right() searches/binary_search.py141-178 - 将元素插入最右侧位置二分搜索模块包含性能基准测试代码searches/binary_search.py325-351，对不同实现进行比较
来源
排序算法在集合中按特定顺序排列元素。该仓库包含基于比较、基于分布和专门的排序实现。
下表总结了已实现算法的时间和空间复杂度
| 算法 | 最佳情况 | 平均情况 | 最坏情况 | 空间复杂度 | 稳定 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 是 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 否 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 是 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 否 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 是 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 否 |
| Shell Sort | O(n log n) | O(n(log n)²) | O(n(log n)²) | O(1) | 否 |
| Bucket Sort | O(n+k) | O(n+k) | O(n²) | O(n+k) | 是 |
| Bead Sort | O(n) | O(n²) | O(n²) | O(n) | 是 |
| Cocktail Shaker Sort | O(n) | O(n²) | O(n²) | O(1) | 是 |
| Gnome Sort | O(n) | O(n²) | O(n²) | O(1) | 是 |
| 算法 | 最佳情况 | 平均情况 | 最坏情况 | 空间复杂度 | 先决条件 |
|---|---|---|---|---|---|
| 线性搜索 | O(1) | O(n) | O(n) | O(1) | 无 |
| 递归线性搜索 | O(1) | O(n) | O(n) | O(n) | 无 |
| 二分搜索 | O(1) | O(log n) | O(log n) | O(1) | 排序后的集合 |
| 二分搜索（递归） | O(1) | O(log n) | O(log n) | O(log n) | 排序后的集合 |
| 指数搜索 | O(1) | O(log i) | O(log i) | O(log n) | 排序后的集合 |
来源
冒泡排序是一种简单的基于比较的算法，它会重复地遍历列表，比较相邻的元素，并在顺序错误时交换它们。该仓库提供了迭代和递归实现。
实现包含两个主要函数
bubble_sort_iterative：迭代实现bubble_sort_recursive：递归实现主要实现细节
swapped），通过在某次遍历中没有发生交换时提前终止来优化性能。来自sorts/bubble_sort.py4-54的示例实现
来源
快速排序是一种分治算法，它通过从数组中选择一个“枢轴”元素，并将其他元素根据它们小于或大于枢轴的值划分为两个子数组来工作。
该实现使用随机枢轴选择策略，以避免在已排序数组上的最坏情况性能。quick_sort函数负责分区和递归排序。
来自sorts/quick_sort.py16-43的关键实现细节
lesser和greater）来源
归并排序是一种高效、稳定、基于比较的分治排序算法。它将输入数组分成两半，递归地对它们进行排序，然后合并已排序的两半。
实现包含两个关键函数
merge_sort：递归地划分和解决数组merge：合并两个已排序数组的辅助函数来自sorts/merge_sort.py13-49的关键实现细节
来源
堆排序是一种基于比较的排序算法，它使用二叉堆数据结构。它将输入分成已排序区域和未排序区域，并通过提取最大元素并将其插入已排序区域来逐步缩小未排序区域。
实现使用两个主要函数
heapify：确保维护堆属性heap_sort：主排序函数，构建堆并提取元素来自sorts/heap_sort.py6-57的关键实现细节
来源
插入排序是一种简单的排序算法，它一次构建一个已排序的数组。它对小数据集有效，并且经常被用作更复杂算法的一部分。
在sorts/insertion_sort.py27-59中的实现使用了直接方法
来源
选择排序是一种原地比较排序算法。它将输入列表分为两部分：从左到右构建的已排序子列表和剩余未排序项的子列表。
来自sorts/selection_sort.py1-27的关键实现细节
来源
希尔排序是插入排序的泛化，允许交换相距较远的元素。其思想是安排元素列表，使得从任何位置开始，每隔 h 个元素都能得到一个排序列表。
来自sorts/shell_sort.py6-31的关键实现细节
来源
桶排序是一种分布排序，它通过将数组的元素分布到多个桶中来工作。然后，每个桶都使用不同的排序算法进行单独排序，或通过递归地应用桶排序算法进行排序。
来自sorts/bucket_sort.py34-67的关键实现细节
来源
该仓库还包含几种专用排序算法
珠子排序 sorts/bead_sort.py - 一种自然排序算法，仅适用于非负整数。
鸡尾酒排序 sorts/cocktail_shaker_sort.py - 冒泡排序的一种变体，双向排序，在某些情况下可以减少所需传递次数。
地精排序 sorts/gnome_sort.py - 一种简单的排序算法，类似于插入排序，但一次将元素向后移动一个位置。
拓扑排序 sorts/topological_sort.py - 一种基于图的排序算法，用于对有向无环图进行排序。
摆动排序 sorts/wiggle_sort.py - 将数组重新排列成锯齿形模式，其中 nums[0] < nums[1] > nums[2] < nums[3]...。
来源
许多排序算法的实现都包含基准测试代码和示例。例如，冒泡排序实现比较了迭代版本和递归版本的性能。
要在自己的代码中使用这些排序算法，只需导入所需的函数并将集合传递给它即可。
大多数排序实现遵循相同的接口模式。
来源