递归

在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数。

n-皇后

    在n×n格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

解析：定义一个长度为N的数组，数组的每一项值表示皇后所在的的行数，具体算法解释如（）。

class Recursion:    '''    递归    '''    def __init__(self):        pass    '''    name: n皇后算法    desc：在n×n格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。    '''    def n_queens(self, A, cur=0):        '''        :param A:  长度为n的数组，存放每一列皇后所在的行数        :param cur: 当前摆放的位置        :return: none        '''        if cur == len(A):            # 摆放完所有位置，queen数组记录八个皇后各自的列数            print(A)            return 0        for col in range(len(A)):            # 初始赋值            A[cur], flag = col, True            for row in range(cur):                # 当前点不在前一个点的同一行，也不在同一斜线                # abs(col - A[row]) == cur - row可以理解成点斜式:y-y0=k(x-x0)，其中k=1                # => y-x = y0-x0 即等式成立，那么（y0,x0）在直线上                # 加绝对值是因为可能正斜线与反斜线，斜率大小相等                if A[row] == col or abs(col - A[row]) == cur - row:                    flag = False                    break            if flag:                # 递归                self.n_queens(A, cur + 1)eight_queens = Recursion()eight_queens.n_queens([None]*8)

总结：递归运算主要注意两个条件，一个是初始状态，二是变化量，其中变化量一定是能确保函数结束的。

分治

分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

二分搜索

二分搜索法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法运算终止。

class DivideAndConquer:    '''    分治    '''    def __init__(self):        pass    '''    name: 二分搜索算法    desc: 将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法运算终止。    '''    def binary_search(self, li, elem):        '''        :param li: 有序数列        :param elem: 待查找元素        :return: 元素位置        '''        length = len(li)        left = 0        right = length - 1        while left <= right:            middle = int((left + right) / 2)            if elem == li[middle]:                return middle            if elem > li[middle]:                left = middle + 1            else:                right = middle - 1        return None

归并排序

归并排序基于这样一个技巧：将 2 个大小为 N/2 的已排序序列合并为一个 N 元素已排序序列仅需要 N 次操作。这个方法叫做归并。（）

class DivideAndConquer:    '''    分治    '''    def __init__(self):        pass    '''    name: 归并排序    desc: 其思想时将待排序的n个元素分成大小大致相同的两个子集，分别对两个子集进行排序，最终将排序好的子集合并    '''    def merge(self, letf, right):        # 合并ul[left]和ul[right]到merge        merge = []        while len(letf) > 0 and len(right) > 0:            if letf[0] <= right[0]:                merge.append(letf.pop(0))            else:                merge.append(right.pop(0))        if len(letf) <= 0:            merge.extend(right)        else:            merge.extend(letf)        return merge

快速排序

基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。（）

class DivideAndConquer:    '''    分治    '''    def __init__(self):        pass'''    name: 快速排序    desc: 首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。    '''    def partition(self, ul, s, e):        '''        设置准基，把无序列表分成左右两个列表，其中左列表的值都小于有列表的值        :param ul:        :return:  分裂的基准        '''        i, j = s, e + 1        elem = ul[s]        while True:            # 将 
    
     elem 的移到右边            i += 1            while ul[i] < elem and i < e:                i += 1            j -= 1            while ul[j] > elem:               j -= 1            if i >= j:                break            ul[i], ul[j] = ul[j], ul[i]        ul[s], ul[j] = ul[j], elem        return j    def quick_sort(self, ul, s, e):        if s < e:            r = self.partition(ul, s, e)            self.quick_sort(ul, s, r-1)            self.quick_sort(ul, r+1, e)        return ul