算法导论-第二章

打算重温《算法导论》，然后把书中的伪代码努力变成Python代码，其实看MIT《算法导论》的公开课更有意思。

画外音：其实是当年没好好去上课…现在从头开始补-_-||

心诚则灵

                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         佛祖保佑       永无BUG

插入排序

原书P26，中文版P14：

def insertion_sort(seq):
    length = len(seq)
    counter = 1
    while counter < length:
        key = seq[counter]
        former = counter - 1
        while former > -1 and seq[former] > key:
            seq[former+1] = seq[former]
            former -= 1
        seq[former+1] = key
        counter += 1
    
sequence = [5, 2, 4, 6, 1, 3]
insertion_sort(sequence)
print(sequence)

选择排序

在习题2.2-2中：

def selection_sort(seq):
    for num_counter, num_temp in enumerate(seq):
        min_number = num_temp
        min_pos = num_counter
        for min_counter, min_temp in enumerate(seq[num_counter+1:]):
            if min_number > min_temp:
                min_number = min_temp
                min_pos = min_counter + num_counter + 1
        seq[num_counter], seq[min_pos] = seq[min_pos], seq[num_counter]
    
sequence = [5, 2, 4, 6, 1, 3]
selection_sort(sequence)
print(sequence)

归并排序

原书P31，中文版P19：

def merge_sort(seq):
    length = len(seq)
    if length < 2:
        return seq
    mid = length // 2
    s1 = merge_sort(seq[:mid])
    s2 = merge_sort(seq[mid:])
    templ = []
    i, j = 0, 0
    while i < len(s1) and j < len(s2):
        if s1[i] < s2[j]:
            templ.append(s1[i])
            i += 1
        else:
            templ.append(s2[j])
            j += 1
    templ += s1[i:]
    templ += s2[j:]
    return templ
    
sequence = [5, 2, 4, 6, 1, 3]
print(merge_sort(sequence))
    

最大子数组

原书P68，中文版P38

def enumerate_reversed(sequence, start=None):
    n = len(sequence)-1 if start is None else start
    for elem in reversed(sequence):
        yield n, elem
        n -= 1
    
def find_max_crossing_subarray(array, mid):
    left_max, left_pos, left_sum = array[mid-1], mid-1, 0
    for left_elem_idx, left_elem in enumerate_reversed(array[:mid]):
        left_sum += left_elem
        if left_sum > left_max:
            left_pos = left_elem_idx
    right_max, right_pos, right_sum = array[mid], mid, 0
    for right_elem_idx, right_elem in enumerate(array[mid:]):
        right_sum += right_elem
        if right_sum > right_max:
            right_pos = right_elem_idx
    return array[left_pos:mid+right_pos+1]
    
def find_maximum_subarray(array):
    if len(array) == 1:
        return array
    else:
        mid = len(array) // 2
        left_array = find_maximum_subarray(array[:mid])
        right_array = find_maximum_subarray(array[mid:])
        cross_array = find_max_crossing_subarray(array, mid)

        left_sum, right_sum, cross_sum = sum(left_array), sum(right_array), sum(cross_array)
        if left_sum > right_sum and left_sum > cross_sum:
            return left_array
        elif right_sum > left_sum and right_sum > cross_sum:
            return right_array
        return cross_array
    
test_array = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
maximum_array = find_maximum_subarray(test_array)
print(maximum_array)
    

注：应该避免在Python代码中，修改处于迭代中的容器，我这么写只是想高度还原伪代码而已╮(╯_╰)╭。

-EOF-