分治算法（Divide and conquer algorithms）：分而治之。

  • 将要解决的问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题
  • 求解各个子问题,由于各个子问题和原问题的形式相同,只是规模较小,因此当子问题划分的足够小时,我们就可以用较为简单的方法去解决.
  • 按照原问题的要求,将子问题的解逐层的合并构成原问题的解.

1 归并排序

  1. from heapq import merge
  3. def merge_sort(array: list):
  4.     """归并排序
  5.     Example：
  6.     >>> myArray = [36, 25, 48, 12, 25, 65, 43, 57]
  7.     >>> [12, 25, 25, 36, 43, 48, 57, 65]
  8.     """
  9.     if len(array) <= 1:
  10.         return array
  11.     else:
  12.         middle = len(array) // 2
  13.         left = merge_sort(array[:middle])
  14.         right = merge_sort(array[middle:])
  15.         return list(merge(left, right))
  1. def merge_sort(lst):
  2.     if len(lst) <= 1:
  3.         return lst
  5.     def merge(left, right):
  6.         merged = []
  8.         while left and right:
  9.             merged.append(left.pop(0) if left[0] <= right[0] else right.pop(0))
  11.         while left:
  12.             merged.append(left.pop(0))
  14.         while right:
  15.             merged.append(right.pop(0))
  17.         return merged
  19.     middle = int(len(lst) / 2)
  20.     _left = merge_sort(lst[:middle])
  21.     _right = merge_sort(lst[middle:])
  22.     return merge(_left, _right)

2 连续子列表的最大和

2.1 遍历法

  1. def max_sub_array(nums):
  2.     """遍历法,(On)
  3.     >>> myArray = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
  4.     >>> print(max_sub_array(myArray))
  5.     >>> 6
  6.     """
  7.     one_sum = 0
  8.     max_sum = nums[0]
  9.     for i in range(len(nums)):
  10.         one_sum += nums[i]
  11.         max_sum = max(max_sum, one_sum)
  12.         if one_sum < 0:
  13.             one_sum = 0
  14.     return max_sum

2.2 分治法

  1. def max_sub_array(nums):
  2.     """分治法
  3.     """
  4.     if not nums:
  5.         return
  6.     if len(nums) == 1:
  7.         return nums[0]
  9.     middle = len(nums) // 2
  10.     left_sum = max_sub_array(nums[:middle])
  11.     right_sum = max_sub_array(nums[middle:])
  13.     left_middle_sum, right_middle_sum, max_left, max_right = 0, 0, 0, 0
  14.     for i in range(middle - 1, -1, -1):
  15.         left_middle_sum += nums[i]
  16.         max_left = max(left_middle_sum, max_left)
  17.     for i in range(middle + 1, len(nums), 1):
  18.         right_middle_sum += nums[i]
  19.         max_right = max(right_middle_sum, max_right)
  20.     return max(left_sum, max_left + nums[middle] + max_right, right_sum)

2.2 动态规划

  1. def max_sub_array(array):
  2.     """ 动态规划 
  3.     """
  4.     if not array:
  5.         return
  6.     if len(array) == 1:
  7.         return array[0]
  9.     dp = res = array[0]
  11.     for i in range(1, len(array)):
  12.         dp = max(array[i], dp + array[i])
  13.         res = max(dp, res)
  14.     return res

3 二分查找

  1. def binary_search(array: list, item: int) -> int:
  2.     """二分查找
  3.     Example:
  4.     >>> myArray = [1, 3, 5, 7, 9]
  5.     >>> print(binary_search(myArray, 5))
  6.     >>> 2
  7.     """
  8.     low = 0
  9.     high = len(array) - 1
  11.     while low <= high:
  12.         mid = (low + high) // 2
  13.         guess = array[mid]
  15.         if guess == item:
  16.             return mid
  17.         if guess > item:
  18.             high = mid - 1
  19.         else:
  20.             low = mid + 1
  21.     return -1