分治算法 -Python刷题笔记

• 分而治之
  分治算法 Divide and Conquer
  就是把复杂问题分解成大小合适的子问题然后求解，最后把子问题解合并为原问题的解。

• 分治法特征：

  • 问题的规模缩小到一定的程度就可以容易地解决
  • 问题具有最优子结构性质
  • 子问题的解可以合并为该问题的解
    这条不满足但是前两条都满足的话可以考虑使用贪心算法或者动态规划
  • 子问题是相互独立的，即子问题之间不包含公共的子子问题
    如不独立，分治法也可用但是效率不高，一般使用动态规划

快速排序

• 时间复杂度 O(nlogn)

• partition
  input：一个list
  return：小于pivot的部分，list的枢纽pivot， 大于pivot的部分

• quick_sort
  input：list
  利用递归，调用 partition 不断分解list，最后合并所有部分

'''
pivot枢纽，low和high为起点终点
'''

#划分分区（非就地划分）
def partition(nums=list):

    pivot = nums[0]                             #挑选枢纽
    lo = [x for x in nums[1:] if x < pivot]     #所有小于pivot的元素
    hi = [x for x in nums[1:] if x >= pivot]    #所有大于pivot的元素
    return lo,pivot,hi

#快速排序
def quick_sort(nums=list):

    #被分解的Nums小于1则解决了
    if len(nums) <= 1:
        return nums

    #分解    
    lo,pivot,hi = partition(nums)

    # 递归（树），分治，合并
    return quick_sort(lo) + [pivot] + quick_sort(hi)

lis = [7, 5, 0, 6, 3, 4, 1, 9, 8, 2]
print(quick_sort(lis)) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

归并排序（二分排序）

归并排序图解

• 分割：递归地把当前序列 平均分割 成两半。
• 集成：在 保持元素顺序 的同时将上一步得到的 子序列集成 到一起（归并）。

# 归并排序
def merge(arr, l, m, r): 
    n1 = m - l + 1
    n2 = r- m 
  
    # 创建临时数组
    L = []
    R = []
  
    # 拷贝数据到临时数组 L[] 和 R[] 
    for i in range(0 , n1): 
        L.append(arr[l + i])
    for j in range(0 , n2): 
        R.append(arr[m + 1 + j])
  
    # 归并临时数组到 arr[l..r] 
    i = 0     # 初始化第一个子数组的索引
    j = 0     # 初始化第二个子数组的索引
    k = l     # 初始化归并子数组的索引
  
    # 判断大小 依次填充到 arr[]
    while i < n1 and j < n2 : 
        if L[i] <= R[j]: 
            arr[k] = L[i] 
            i += 1
        else: 
            arr[k] = R[j] 
            j += 1
        k += 1
  
    # 拷贝 L[] 的保留元素
    while i < n1: 
        arr[k] = L[i] 
        i += 1
        k += 1
  
    # 拷贝 R[] 的保留元素
    while j < n2: 
        arr[k] = R[j] 
        j += 1
        k += 1
  
def mergeSort(arr,l,r): 
    if l < r: 
        m = int((l+(r-1))/2)
        mergeSort(arr, l, m)    # 先排左
        mergeSort(arr, m+1, r)  # 排右
        merge(arr, l, m, r)     # 整个排
  
  
arr = [12, 11, 13, 5, 6, 7] 
print(arr)
mergeSort(arr,0,len(arr)-1)
print ("\n排序后的数组") 
print(arr)

面试题51. 数组中的逆序对

Reference

[1] 分治法及其python实现例子
[2] Python 归并排序 - 菜鸟教程