分治算法 python

分治算法是一种将复杂问题分解成更小的相似子问题，然后递归地解决这些子问题，并最终合并结果的策略。它通常包含三个步骤：分解（Divide）、求解（Solve）和合并（Combine）。在Python中，可以很容易地应用分治法来处理排序、搜索、图形分割等问题。

例如，对于快速排序算法，就是一个典型的分治例子。它首先选择一个基准元素，然后将数组分成两部分，一部分所有元素都小于基准，另一部分都大于或等于基准。接着对这两部分递归地执行同样的操作，最后将结果合并起来。

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

# 使用示例
arr = [3,6,8,10,1,2,1]
sorted_arr = quicksort(arr)