基本算法之分治
分而治之就是分治法的基本思想。简单来说，就是将一个大问题分解成若干个小问题，分别对这几个小问题进行求解，一直这样分解下去，直到解决这个大问题。能用分治法的题目需要符合以下两个特征：
- 平衡子问题，子问题的规模大致相同；
- 独立子问题：子问题之间相互独立。
在我们之前讲过的二分法就是分治法的一个典型案例。分治法的经典应用有汉诺塔、归并排序，快速排序。
汉诺塔
传说中有三根柱子（A、B、C），开始时所有的盘子都叠在第一根柱子上，盘子的大小都不相同，都是小的在上，大的在下。目标是把所有盘子从第一根（A）柱子移动到第三根（C）柱子上，但是在移动的过程中有两个限制：
- 每次只能移动一个盘子。
- 大盘子不能放在小盘子上面。
输入要求：两个正整数，第一个正整数N是要移动的牌子总数，第二个正整数M是移动步骤的第M步。
输出要求：共两行，第一行输出第M步的移动方式，例如：#2: A->B，第二行输出最少的移动步数。
汉诺塔问题可以分解成两个子问题：
- 把x杆的n-1个盘子移动到y杆，然后把第n个大盘移动到z杆；
- 把y杆上的n-1个小盘移动到z杆。
【汉诺塔小游戏和递归思想-哔哩哔哩】 https://b23.tv/HFzxZQ2
step = 0
m,n = 0,0
def Hanoi(x,y,z,n):
global step,m
if n==1:
if m == step + 1:
print(f'#{step + 1}: {x}->{z}')
step += 1
else:
Hanoi(x,z,y,n-1)
if m == step + 1:
print(f'#{step + 1}: {x}->{z}')
step += 1
Hanoi(y,x,z,n-1)
n,m = map(int, input().split())
Hanoi('A','B','C',n)
print(step)
归并排序
如何使用分治法来解决排序问题？根据分治法的分解、解决、合并三个步骤，我们可以这样想：
- 分解：把无序的数组分成两部分，对于每一个部分再分解成更小的两个部分；
- 解决：分解到不能再分解，然后进行排序；
- 合并：排完序的数组两两合并。
归并排序就是体现分治法思想例子，
值得注意的是，在“解决”这一步骤中，由于归并排序的子序列只包含一个数，其实不用排序。而最重要的时合并的步骤，合并的步骤需要进行排序。
分析得到归并排序的时间复杂度是O(n\log_2n)，空间复杂度为O(n)。
def merge_sort(l:list):
if len(l) > 1:
mid = len(l) // 2; # 找到中间的索引
left = l[0:mid] # 分为左右两个数组
right = l[mid:]
merge_sort(left) # 分割成更小的数组
merge_sort(right)
# 合并
i,j,k = 0,0,0 # 双指针法合并
while i < len(left) and j < len(right):
if left[i] > right[j]:
l[k] = right[j]
k += 1
j += 1
else:
l[k] = left[i]
k += 1
i += 1
# 将剩余数组合并
while i<len(left):
l[k] = left[i]
k += 1
i += 1
while j<len(right):
l[k] = right[j]
k += 1
j += 1
return l
l = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(merge_sort(l))
在大多数需要排序的情况下，我们只需要使用自带的排序函数就行，但是有时候我们需要给排序函数加上一些自己的功能，这种情况下就需要我们手写代码。
快速排序
快速排序的思路就是把序列分成左、右两个部分，使左边所有的数都比右边的数小，递归这个过程，直到不能再分为止。
下图介绍了一种很容易进行划分的方法：
对于复杂度：快速排序的总复杂度是O(n\log_2n)。在极端情况下，左部分只有一个数，剩下的都在右部分，此时的总复杂度为O(n^2)。所以，快速排序是不稳定的。
在Python中，划分的代码编写起来十分容易，这里用第一个元素作为基准元素：
def quicksort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
less_than_pivot = [x for x in arr[1:] if x <= pivot]
greater_than_pivot = [x for x in arr[1:] if x > pivot]
return quicksort(less_than_pivot) + [pivot] + quicksort(greater_than_pivot)
# 示例用法
my_list = [3, 6, 8, 10, 1, 2, 1]
sorted_list = quicksort(my_list)
print(sorted_list)
评论区