python 算法

python 算法

1.汉诺塔

def hanoi(n, a, b, c):
    if n > 0:
        hanoi(n-1, a, c ,b)
        print('moving from {} to {}'.format(a, c))
        hanoi(n-1, b, a, c)

2.列表查找

def line_search(li, val):
    for index, x in enumerate(li):
        if x == val:
            #print(index)
            return index
    else:
        return None

3.二分查找

def bina_search(li, val):
    left = 0
    right = len(li) - 1
    while left <= right:
        mid = (left + right) // 2
        if li(mid) == val:
            return mid
        elif li(mid) > val:
            right = mid - 1
        else:
            left = mid + 1
    else:
        return None

4.冒泡排序

def bubble_sort(li):
    for i in range(len(li)-1):
        flag = False
        for j in range(len(li)-1-i):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
                flag = True
        if not flag:
            return 

5.1选择排序

def select_sort(li):
    li_new = []
    for i in range(len(li)):
        min_val = min(li)
        li_new.append(min_val)
        li.remove(min_val)
    return li_new
        

5.2选择排序

def select_sort(li):
    for i in range(len(li)-1):
        min_loc = i
        for j in range(i+1, len(li)):
            if li(j) < li(min_loc):
                min_loc = j
        li[i], li[min_loc] = li[min_loc], li[i]

6.插入排序

def insert_sort(li):
    for i in range(1, len(li)):
        j = i - 1
        temp = li[i]
        while j >= 0 and li[j] > temp:
            li[j+1] = li[j]
            j -= 1
        li[j+1] = temp

7.快速排序

def partition(li, left, right):
    temp = li[left]
    while left < right:
        while left < right and li[right] >= temp:
            right -= 1
        li[left] = li[right]
        while left < right and li[left] <= temp:
            left += 1
        li[right] = li[left]
    li[left] = temp
    return left

def quick_sort(li, left, right):
    if left < right:
        mid = partition(li, left, right)
        quick_sort(li, left, mid-1)
        quick_sort(li, mid+1, right)