分治算法思想

在编程过程中，经常遇到处理数据相当多、求解过程比较复杂、直接求解会比较耗时的问题。在求解这类问题时，可以采用各个击破的方法。具体做法是：先把这个问题分解成几个较小的子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个大问题的解。如果这些子问题还是比较大，可以继续把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。

解题步骤

1. 分解，将要解决的问题划分成若干个规模较小的同类问题。
2. 求解，当子问题划分得足够小时，用较简单的方法解决。
3. 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

求顺序表中最大值

# 返回两个值中的最大值
def get_max(max_list):
    if len(max_list) > 1 and max_list[0] <= max_list[1]:
        return max_list[1]
    else:
        return max_list[0]

def solve(init_list):
    n = len(init_list)
    if n <= 2:
        return get_max(init_list)

    left_list, right_list = init_list[:n//2], init_list[n//2:]
    left_max, right_max = solve(left_list), solve(right_list)
    return get_max([left_max, right_max])

if __name__ == '__main__':
    test_list = [12, 2, 23, 45, 67, 3, 2, 4, 45, 63, 24, 23]
    print(solve(test_list))  # 67

判断某个元素是否在列表中

def is_in_list(init_list, el):
    return [False, True][init_list[0] == el]

def solve(init_list, el):
    n = len(init_list)
    if n == 1:
        return is_in_list(init_list, el)

    left_list, right_list = init_list[:n//2], init_list[n//2:]
    res = solve(left_list, el) or solve(right_list, el)
    return res

if __name__ == '__main__':
    test_list = [12, 2, 23, 45, 67, 3, 2, 4, 45, 63, 24, 23]
    print(solve(test_list, 45))  # True
    print(solve(test_list, 5))  # False

找出序列中第 k 小的元素

def partition(seq):
    pi = seq[0]
    lo = [x for x in seq[1:] if x <= pi]
    hi = [x for x in seq[1:] if x > pi]
    return lo, pi, hi

def select(seq, k):
    lo, pi, hi = partition(seq)

    m = len(lo)
    if m == k - 1:
        return pi
    elif m < k - 1:
        return select(hi, k - 1 - m)
    else:
        return select(lo, k)

if __name__ == '__main__':
    test_list = [5, 2, 8, 7, 6, 3, 1, 4, 9, 10, 12, 11]
    print(select(test_list, 7))  # 7
    print(select(test_list, 3))  # 3