常见算法的python实现

• binary search

def search(li, target):
    def binary_search(li, target, left, right):
        # li is a sorted array
        # target is the searching target, which should be unique in the array
        # left and right set the search boundary
        if left <= right:
            mid = (left + right) // 2
            if li[mid] < target:
                return binary_search(li, target, mid, right)
            elif li[mid] > target:
                return binary_search(li, target, left, mid)
            else:
                return mid
        else:
            return -1
    print(binary_search(li, target, 0, len(li)))


search([i for i in range(100)], 6)

• x raised to the n-th power

def power(x, n):
    if n == 0:
        return 1
    t = power(x, n//2)
    if n % 2 == 1:
        return t*t*x
    return t*t

• matrix multiplication - the strassen algorithm

# an amazing method of reducing the number of mutiplication
# coding: utf-8 -*-
# copied from https://blog.csdn.net/shaungyezhai/article/details/52229500
def matrixproduct(a, b):
    def matrixproductmask(mat_a, mat_b):
        if mat_a.row == 1:
            c11 = [[mat_a.mat_list[mat_a.row_list[0]][mat_a.col_list[0]] *
                    mat_b.mat_list[mat_b.row_list[0]][mat_b.col_list[0]]]]
            return Martrix(c11)
        else:
            mat_a11 = mat_a.divide('11')
            mat_a12 = mat_a.divide('12')
            mat_a21 = mat_a.divide('21')
            mat_a22 = mat_a.divide('22')
            mat_b11 = mat_b.divide('11')
            mat_b12 = mat_b.divide('12')
            mat_b21 = mat_b.divide('21')
            mat_b22 = mat_b.divide('22')

            s1 = mat_b12 - mat_b22
            s2 = mat_a11 + mat_a12
            s3 = mat_a21 + mat_a22
            s4 = mat_b21 - mat_b11
            s5 = mat_a11 + mat_a22
            s6 = mat_b11 + mat_b22
            s7 = mat_a12 - mat_a22
            s8 = mat_b21 + mat_b22
            s9 = mat_a11 - mat_a21
            s10 = mat_b11 + mat_b12

            p1 = matrixproductmask(mat_a11, s1)
            p2 = matrixproductmask(s2, mat_b22)
            p3 = matrixproductmask(s3, mat_b11)
            p4 = matrixproductmask(mat_a22, s4)
            p5 = matrixproductmask(s5, s6)
            p6 = matrixproductmask(s7, s8)
            p7 = matrixproductmask(s9, s10)

            c11 = (p5 + p4 - p2 + p6)
            c12 = (p1 + p2)
            c21 = (p3 + p4)
            c22 = (p5 + p1 - p3 - p7)

            return matrixmerge(c11, c12, c21, c22)

    mat_a = Martrix(a)
    mat_b = Martrix(b)
    product = matrixproductmask(mat_a, mat_b)
    return product.mat_list


def matrixmerge(c11, c12, c21, c22):
    mat_list = []
    for i in c11.row_list:
        mat_list.append(c11.mat_list[i] + c12.mat_list[i])
    for i in c21.row_list:
        mat_list.append(c21.mat_list[i] + c22.mat_list[i])
    return Martrix(mat_list)


class Martrix(object):
    def __init__(self, *args):
        if len(args) == 1 and isinstance(args[0], list):
            self.mat_list = args[0]
            self.row = len(args[0])
            self.col = len(args[0][0])
            self.row_list = range(self.row)
            self.col_list = range(self.col)

    def __add__(self, mat2):
        mat_list = [
            [self.mat_list[self.row_list[i]][self.col_list[j]] + mat2.mat_list[mat2.row_list[i]][mat2.col_list[j]]
             for j in range(self.col)] for i in range(self.row)]
        return Martrix(mat_list)

    def __sub__(self, mat2):
        mat_list = [
            [self.mat_list[self.row_list[i]][self.col_list[j]] - mat2.mat_list[mat2.row_list[i]][mat2.col_list[j]]
             for j in range(self.col)] for i in range(self.row)]
        return Martrix(mat_list)

    def divide(self, block):
        result = Martrix()
        result.mat_list = self.mat_list
        result.row = self.row / 2
        result.col = self.col / 2
        dic = {'11': [self.row_list[:result.row], self.col_list[:result.col]],
               '12': [self.row_list[:result.row], self.col_list[result.col:]],
               '21': [self.row_list[result.row:], self.col_list[:result.col]],
               '22': [self.row_list[result.row:], self.col_list[result.col:]]}
        result.row_list = dic[block][0]
        result.col_list = dic[block][1]
        return result


a = [[1, 4, 8, 7], [5, 7, 9, 13], [3, 6, 8, 11], [-1, -3, 5, 3]]
b = [[4, 8, -12, 5], [2, 1, 9, 4], [12, 45, -21, 5], [5, -1, 4, 7]]
c = matrixproduct(a, b)
print(c)

• quick sort

# sort in place and storage efficient
# coding: utf-8


def partition(sort_list: list, left: int, right: int):
    pivot = sort_list[right]
    # choose the right number as the pivot
    i = left
    for j in range(left, right + 1):
        if sort_list[j] <= pivot:
            sort_list[i], sort_list[j] = sort_list[j], sort_list[i]
            i += 1
    return i - 1
    # return the index of pivot


def quick_sort(sort_list: list, left: int = None, right: int = None) -> object:
    left = 0 if isinstance(left, (int, float)) == 0 else left
    right = len(sort_list) - 1 if isinstance(right, (int, float)) == 0 else right
    # these if-else sentences simplify the input of function
    if left < right:  # important judgement
        x = partition(sort_list, left, right)
        quick_sort(sort_list, left, x - 1)
        quick_sort(sort_list, x + 1, right)
    return sort_list


s_list = [1, 2, 0, 10, 14, 12, 3, 5, 4, 9, 6, 8, 7, 11, 13]
sorted_list = quick_sort(s_list)
print(sorted_list)