Python实现常见算法

曾用python实现的小算法，防止以后找不到了，今后再用python实现的算法，也放在这里

排序相关

直接选择排序

# 直接选择排序
def select_sort(array):
    if not array:
        return []
    for i in range(len(array) - 1, 0, -1):
        large = array[0]
        pos = 0
        for j in range(1, i + 1):
            if array[j] > large:
                pos = j
                large = array[j]
        array[pos], array[i] = array[i], array[pos]
    return array

冒泡排序

# 冒泡排序
def bubble_sort(array):
    if not array:
        return []
    for i in range(len(array) - 1, 0, -1):
        for j in range(i):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
    return array

快速排序

# 快速排序
def quick_sort(array):
    if not array:
        return []
    quick_sort_temp(array, 0, len(array) - 1)
    return array


def quick_sort_temp(array, low, high):
    if low >= high:
        return
    flag = array[low]
    l, h = low + 1, high
    while l < h:
        while h > l and array[h] >= flag:
            h -= 1
        while l < h and array[l] < flag:
            l += 1
        if l != h:
            array[l], array[h] = array[h], array[l]
    array[low], array[l] = array[l], array[low]
    quick_sort_temp(array, low, l - 1)
    quick_sort_temp(array, l + 1, high)

堆排序

# 堆排序
def heep_sort(array):
    if not array:
        return []
    for i in range(len(array) - 1, 0, -1):
        heep_sort_up(array, i)
    for i in range(len(array) - 1, 0, -1):
        array[0], array[i] = array[i], array[0]
        heep_sort_down(array, i - 1, 0)
    return array


def heep_sort_up(array, pos):
    while pos > 0:
        father = (pos - 1) / 2
        if array[father] <= array[pos]:
            array[father], array[pos] = array[pos], array[father]
        pos = father


def heep_sort_down(array, max_pos, root):
    if root > max_pos:
        return
    large = root
    left, right = root * 2 + 1, root * 2 + 2
    if left <= max_pos and array[large] < array[left]:
        large = left
    if right <= max_pos and array[large] < array[right]:
        large = right
    if large != root:
        array[large], array[root] = array[root], array[large]
        heep_sort_down(array, max_pos, large)

斐波那契数列

斐波那契数列-1

# 斐波那契数列 o(n^2)
fab = lambda n: fab(n - 1) + fab(n - 2) if n > 1 else n

斐波那契数列-2

# 斐波那契数列 o(n^2)
def fabN(n):
    return fabN(n - 1) + fabN(n - 2) if n > 1 else n

斐波那契数列-3

# 斐波那契数列 o(n)
def fabN1(n):
    if n > 1:
        temp = [0, 1]
        while len(temp) <= n:
            temp.append(temp[len(temp) - 1] + temp[len(temp) - 2])
        return temp[len(temp) - 1]
    else:
        return n

二分查找

# 二分查找
def bin_search(array, start, end, value):
    if not array or start < 0 or end >= len(array):
        return -1
    if start >= end:
        return -1
    mid = (start + end) >> 1
    if array[mid] == value:
        return mid
    elif array[mid] > value:
        return bin_search(array, start, mid, value)
    else:
        return bin_search(array, mid, end, value)

字符串

回文字符串

# 回文字符串
def is_huiwen(data):
    if not data:
        return False
    size = len(data)
    for i in range(size / 2):
        if data[i] != data[size - 1 - i]:
            return False
    return True