分治算法学习笔记——二分查找、全排列、归并排序、快速排序、汉诺塔

时间:2020-9-2 作者:admin


分治算法(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

案例之归并排序

归并排序

将两个或两个以上的有序数组合并成一个新的有序数组,即,将待排序序列分成若干个子序列,每个子序列是有序的,然后再把有序子序列合并为整体有序序列

实现方法——迭代法:

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  4. 重复步骤 3 ,直到某一个指针到达序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

实现方法——递归法:

  1. 将序列中每相邻两个数字进行归并操作,形成 [n/2] 个序列,排序后每个序列都包含两个元素
  2. 将上述序列再次合并,形成 [n/4] 个序列,每个序列中的元素数倍增
  3. 重复步骤 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)

案例之快速排序

快速排序

快速排序使用分治算法来吧一个序列分为较小和较大的两个序列,然后递归地排序两个序列

实现步骤:

  1. 挑选基准值:从数列中挑出一个值,作为“基准”(pivot)
  2. 分割:重新排序数列,所有比基准值小的元素摆放在基准的前面,所有比基准大的元素摆放在基准的后面(与基准相等的元素可以放在任何一边);分割完成后,对基准值的排序也就完成了
  3. 递归排序子序列:递归地将小于基准值元素的子序列和大于基准值元素的子序列排序

递归到最底部的判断条件是: 数列的大小为 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个座上始终保持:大在上,小在下

问题分析

  1. 如果只有一个盘子,则不需要借助C,直接从A移动到B
  2. 如果只有两个盘子,则可以先把A的最上面一个盘子2移动到C;将盘子1移动到B;再讲盘子2移动到B。;这说明了借助C可以将2个盘子从A移动到B;同样,也说明借助B可以将2个盘子从A移动到C
  3. 如果有3个盘子,那么根据2个盘子的结论,可以借助B将盘子1上的两个盘子(盘子2和盘子3)从A移动到C;将盘子1从A移动到B,A则变为空座;借助A座,将C上的两个盘子移动到B
  4. 以此类推,上述思路可以扩展到 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')
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。