这个系列的课程之前学过一遍，但是笔记没有整理完，最近在复习，准备把内容再学习一遍，这次准备实现每周所介绍的全部算法，这里是第一周的内容。

课程地址：https://www.coursera.org/specializations/algorithms

Karatsuba Mulplication

import numpy as np

def Karatsuba_Mulplication(x, y):
    '''
    输入x, y为字符串，首先补0，使得数字长度一样
    '''
    #预处理，使得长度一样
    n1 = len(x)
    n2 = len(y)
    n = max(n1, n2)
    if (n1 < n2):
        x = "0" * (n2 - n1) + x
    else:
        y = "0" * (n1 - n2) + y
    
    #个位数
    if (n == 1):
        return int(x) * int(y)
    else:
        k = n // 2
        #将数分为前l位和剩余部分
        l = n - k
        u = 10 ** k
        a = x[:l]
        b = x[l:]
        c = y[:l]
        d = y[l:]
        ab = str(int(a) + int(b))
        cd = str(int(c) + int(d))
        #递归
        ac = Karatsuba_Mulplication(a, c)
        bd = Karatsuba_Mulplication(b, d)
        abcd = Karatsuba_Mulplication(ab, cd)
        #合并结果
        adbc = abcd - ac - bd
        res = u ** 2 * ac + u * adbc + bd
        
        return res

#测试
N = 1000
Max = 1e5

for i in range(N):
    x = np.random.randint(0, Max)
    y = np.random.randint(0, Max)
    z = x * y
    #转换为字符串
    x1 = str(x)
    y1 = str(y)
    z1 = Karatsuba_Mulplication(x1, y1)
    
    print(z == z1)

Merge Sort

import numpy as np

def Merge(A, l, m, r):
    """
    l, ..., m为第一部分
    m + 1, ..., r为第二部分
    """
    #存储结果
    C = []
    #索引
    i = l
    j = m + 1
    while ((i <= m) and (j <= r)):
        if (A[i] < A[j]):
            C.append(A[i])
            i += 1
        else:
            C.append(A[j])
            j += 1
    #处理剩余部分
    while (i <= m):
        C.append(A[i])
        i += 1
    while (j <= r):
        C.append(A[j])
        j += 1
    #更新
    A[l: (r + 1)] = C

def MSort(A, l, r):
    '''
    对l, ... , r排序
    '''
    if (l < r):
        #print(l, r)
        m = (l + r) // 2
        MSort(A, l, m)
        MSort(A, m + 1, r)
        Merge(A, l, m, r)
        
def Merge_Sort(A):
    n = len(A)
    MSort(A, 0, n - 1)

#测试
N = 1000
Max = 1e5
data = np.random.randint(0, Max, size=N)
data_sort = np.sort(data)
#排序
Merge_Sort(data)
#测试结果
print(np.sum(data != data_sort))