【第七天】零基础入门刷题Python-算法篇-数据结构与算法的介绍-一种常见的分治算法（持续更新）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

提示：这里可以添加本文要记录的大概内容：

第一天Python数据结构与算法的详细介绍
第二天五种常见的排序算法
第三天两种常见的搜索算法
第四天两种常见的递归算法
第五天一种常见的动态规划算法
第六天一种常见的贪心算法
第七天一种常见的分治算法

提示：以下是本篇文章正文内容，下面案例可供参考

一、Python数据结构与算法的详细介绍

1.Python中的常用的分治算法

以下是Python中的一些常用算法：

2. 分治算法

分治算法：
将问题划分为几个规模较小的子问题分别解决，然后将子问题的解合并得到原问题的解。快速排序和归并排序是分治算法的典型例子。

3.详细的分治代码

1）一种常见的分治算法

def quick_sort(arr):# 快速排序的主函数def partition(low, high):# 选择最右边的元素作为基准pivot = arr[high]i = low - 1  # 较小元素的索引for j in range(low, high):# 如果当前元素小于或等于基准if arr[j] <= pivot:i += 1# 交换arr[i]和arr[j]arr[i], arr[j] = arr[j], arr[i]# 交换arr[i + 1]和arr[high] (或基准)arr[i + 1], arr[high] = arr[high], arr[i + 1]return i + 1# 基本情况：如果数组为空或只有一个元素，则直接返回if len(arr) <= 1:return arrelse:# 递归地对数组进行排序pivot_index = partition(0, len(arr) - 1)left_arr = quick_sort(arr[:pivot_index])right_arr = quick_sort(arr[pivot_index + 1:])# 合并排序后的数组（这里实际上没有真正的合并操作，因为数组是就地排序的）# 但为了保持函数调用的完整性，我们仍然返回合并后的结果（即原数组）return left_arr + [arr[pivot_index]] + right_arr# 注意：在实际应用中，为了效率，我们通常不会真的将数组拆分再合并，
# 因为Python的列表切片操作是O(n)时间复杂度的。这里的返回语句只是为了演示分治的思想。
# 在实际实现中，我们会在原地对数组进行排序，避免额外的空间开销。# 归并排序的实现
def merge_sort(arr):# 归并排序的主函数def merge(left, right):sorted_array = []i = j = 0# 合并两个已排序的数组while i < len(left) and j < len(right):if left[i] < right[j]:sorted_array.append(left[i])i += 1else:sorted_array.append(right[j])j += 1# 添加剩余的元素（如果有）sorted_array.extend(left[i:])sorted_array.extend(right[j:])return sorted_array# 基本情况：如果数组为空或只有一个元素，则直接返回if len(arr) <= 1:return arrelse:# 找到数组的中间点，将数组分为两部分mid = len(arr) // 2left_half = merge_sort(arr[:mid])right_half = merge_sort(arr[mid:])# 合并两个已排序的部分return merge(left_half, right_half)# 测试代码
if __name__ == "__main__":test_array = [38, 27, 43, 3, 9, 82, 10]print("Original array:", test_array)# 使用快速排序quick_sorted_array = quick_sort(test_array[:])  # 使用切片创建数组的副本以避免修改原数组print("Quick sorted array:", quick_sorted_array)# 使用归并排序merge_sorted_array = merge_sort(test_array[:])  # 同样使用切片print("Merge sorted array:", merge_sorted_array)

总结

提示：这里对文章进行总结：
例如：以上就是今天要讲的内容，本文简单介绍一种常见的分治算法。