分治算法（Divide and Conquer）
算法
分治，“分而治之”，即把一个复杂的问题分成两个或者更多的相同的或者相似的子问题，再把子问题分成更小的子问题，直到最后的子问题可以简单的求解，原问题的解就是子问题解的合并
基本思想
分治算法在每一层的递归上都有三个步骤：
**分解：**将原问题分解为规模更小、相互独立且与原问题形式相同的子问题
**求解：**如果子问题的规模足够小，可以很容易解决则直接解决，否则，进入下一层递归
**合并：**将求得的子问题的解合并为上一个原问题的解，直到合并为最初原问题的解
适用问题
1、该问题的规模缩小的一定程度可以比较简单地解决
2、该问题可以分解为若干规模较小的相同问题
3、利用该问题分解出的子问题的解可以合并为该问题的解
4、该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题
时间复杂度
分治算法将规模为 n 的问题分为 k 个规模为 n/k 的子问题解决。设分解阈值为 n0 = 1
且求解规模为 1 的问题需耗费 1 个单位时间；再设将原问题分解为 k 个子问题，以及合并 k 个子问题的解合并为原问题的解需要用 f(n) 个单位时间；用 T(n) 表示使用该分治算法求解规模为 n 的问题所需的时间，则有：
T(n) = k*T(n/k) + f(n)
案例之二分查找
二分查找是典型的分治算法的应用，将原有的有序数列划分为左右两个子序列，然后再对两个子序列中的其中一个进行划分，直到查找成功
算法流程
二分查找的前提：必须是有序数列
算法流程：（查找一个数）
1、选择一个标志 i 将数列分为左右两个数列
2、判断 L[i] 是否与要查找的数 ans 相等，相等则返回 i
3、否则，判断 L[i] 与 ans 的大小
4、基于第三步的结果，决定之后是向左寻找还是向右寻找
5、递归，直到找到数 ans，或者确定数组 L 中找不到
代码示例
''' 最基础的二分查找算法 在一个有序的数列中，寻找特定元素的位置 如果找到搜索的数，则返回其索引，否则返回 None '''
def basic_BinarySearch(search_list, item):
low = 0
high = len(search_list)-1
while low <= high:
# 防止 mid 计算溢出
mid = low + (high-low)//2
guess = search_list[mid]
if guess == item:
return mid
elif guess > item:
high = mid - 1
else:
low = mid + 1
return None
''' 寻找左边界的二分查找算法 '''
def left_BinarySearch(search_list, item):
if not search_list:
return None
low = 0
high = len(search_list) # 与 basic 不同
while low < high: # 相比 basic ，没有等号
mid = low + (high-low)//2
if search_list[mid] >= item:
high = mid
else:
low = mid + 1
return low
''' 寻找右边界的二分查找算法 '''
def right_BinarySearch(search_list, item):
if not search_list:
return None
low = 0
high = len(search_list)
while low < high:
mid = low + (high-low)/2
if search_list[mid] <= item:
low = mid + 1
else:
high = mid
return low-1
案例之全排列问题
LeetCode 题目
给定一个 没有重复 数字的序列，返回其所有可能的全排列
示例：
输入:
[1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
问题分析
采用分治思想，首先要把大问题分解为很多子问题，大问题是所有的排列方法；
分解得到的子问题就是：以 1 开头的排列、以 2 开头的排列、以 3 开头的排列；
现有的子问题仍可继续分解，例如，以 1 开头的子问题，确定了 1 的位置，但是没有确定 2、3 的位置，可以继续分解，直到分解成的子问题只有一个数字，不再分解
代码示例
def permute(self, nums: List[int]) -> List[List[int]]:
def fullSort(sort_nums: List[int], start: int, end: int):
if start == end:
res.append(nums[:])
else:
for i in range(start, end):
temp = sort_nums[start]
sort_nums[start] = sort_nums[i]
sort_nums[i] = temp
fullSort(sort_nums, start+1, end)
sort_nums[i] = sort_nums[start]
sort_nums[start] = temp
end = len(nums)
res = []
fullSort(nums, 0, end)
return res
案例之归并排序
归并排序
将两个或两个以上的有序数组合并成一个新的有序数组，即，将待排序序列分成若干个子序列，每个子序列是有序的，然后再把有序子序列合并为整体有序序列
实现方法——迭代法：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤 3 ，直到某一个指针到达序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
实现方法——递归法：
- 将序列中每相邻两个数字进行归并操作，形成 [n/2] 个序列，排序后每个序列都包含两个元素
- 将上述序列再次合并，形成 [n/4] 个序列，每个序列中的元素数倍增
- 重复步骤 2 ，直到所有元素排序
代码示例
def merge(s1, s2, s):
''' 将两个列表 s1 、s2 按顺序融合为一个列表 s :param s1: :param s2: :param s: :return: '''
i = j = 0 # 分别指向 s1 、s2
while i+j < len(s):
if j == len(s2) or (i<len(s1) and s1[i]<s2[j]):
s[i+j] = s1[i]
i += 1
else:
s[i+j] = s2[j]
j += 1
def merge_sort(s):
'''归并排序'''
n = len(s)
if n < 2:
return
mid = n // 2
s1 = s[0:mid]
s2 = s[mid:n]
merge_sort(s1)
merge_sort(s2)
merge(s1, s2, s)
案例之快速排序
快速排序
快速排序使用分治算法来吧一个序列分为较小和较大的两个序列，然后递归地排序两个序列
实现步骤：
- 挑选基准值：从数列中挑出一个值，作为“基准”（pivot）
- 分割：重新排序数列，所有比基准值小的元素摆放在基准的前面，所有比基准大的元素摆放在基准的后面（与基准相等的元素可以放在任何一边）；分割完成后，对基准值的排序也就完成了
- 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序
递归到最底部的判断条件是： 数列的大小为 0 或者 1，此时数列已为有序数列
选取基准的方法对排序的时间性能有决定性影响
代码示例
实现方式1：
def partition(arr, low, high):
i = low-1 # index of minimum-element
pivot = arr[high]
for j in range(low, high):
# if current-element <= pivot
if arr[j] <= pivot:
i = i+1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return (i+1)
def quickSort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
print('results of each step sorting')
print('arra:',arr)
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr, 0, n-1)
print('arr: ', arr)
实现方式2：
# 额外开辟空间
def quick_sort(s):
if len(s)<2:
return
pivot = s[0]
lp = []
ep = []
hp = []
while len(s)>0:
if s[-1] < pivot:
lp.append(s.pop())
elif s[-1] == pivot:
ep.append(s.pop())
else:
hp.append(s.pop())
quick_sort(lp)
quick_sort(hp)
s.extend(lp)
s.extend(ep)
s.extend(hp)
实现方法3：
# 不需要额外开辟空间
def inplace_quick_sort(s, a, b):
if a >= b:
return
pivot = s[b]
left = a
right = b-1
while left <= right:
while left <= right and s[left] < pivot:
left += 1
while left <= right and pivot < s[right]:
right -= 1
if left <= right:
s[left], s[right] = s[right], s[left]
left, right = left+1, right-1
s[left], s[b] = s[b], s[left]
inplace_quick_sort(s, a, left-1)
inplace_quick_sort(s, left+1, b)
案例之汉诺塔（Hanoi Tower）
汉诺塔问题
一个梵塔，塔内有三个盘座A、B、C，A上有64个盘子，盘子大小不等，大在下，小在上。若要把盘子从A移到B，每次只能移动一个，且移动过程中，3个座上始终保持：大在上，小在下
问题分析
- 如果只有一个盘子，则不需要借助C，直接从A移动到B
- 如果只有两个盘子，则可以先把A的最上面一个盘子2移动到C；将盘子1移动到B；再讲盘子2移动到B。；这说明了借助C可以将2个盘子从A移动到B；同样，也说明借助B可以将2个盘子从A移动到C
- 如果有3个盘子，那么根据2个盘子的结论，可以借助B将盘子1上的两个盘子（盘子2和盘子3）从A移动到C；将盘子1从A移动到B，A则变为空座；借助A座，将C上的两个盘子移动到B
- 以此类推，上述思路可以扩展到 n 个盘子的情况，将较小的 n-1 个盘子看做一个整体，也就是我们要求的子问题，初始A上有 n 个盘子，B、C上为空；可以借助B，将A上面的 n-1 个盘子从A移动到C；将A上最大的盘子1移动到B，A为空座；；可以借助B，将C上的 n-2 个盘子从C移动到A；将C上最大的盘子2（从整体看，为第二大）移动到B，C为空座；；…
代码示例
def move(n, source, target):
print('The', n, 'th', 'plate move: ', source, '------>', target)
def hanoi(n, source, temp, target):
if n == 1:
# only one plate, move it directly from source to target
move(n, source, target)
else:
# move the top n-1 plates from source to temp through target
hanoi(n-1, source, target, temp)
# move the n plate(the largest and lowest plate) from source to target
move(n, source, target)
# move the top n-1 plates from temp to target through source
hanoi(n-1, temp, source, target)
hanoi(3, 'A', 'C', 'B')
