【第七天】零基础入门刷题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 arr
    else:
        # 递归地对数组进行排序
        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 += 1
            else:
                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 arr
    else:
        # 找到数组的中间点，将数组分为两部分
        mid = len(arr) // 2
        left_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)

总结

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