19_Python算法

1.冒泡算法

list = [1, 5, 2, 6, 9, 3, 4, 0]
print(len(list))  # 8
conunt = 1
while conunt < len(list):
    for i in range(len(list) - conunt):
        if list[i + 1] <= list[i]:
            list[i], list[i+1] = list[i+1], list[i]
    conunt += 1
print(list)

2.二分查找法

# 二分法查找一个数在不在列表中
lst = [11, 22, 33, 44, 55, 66, 77, 88]

# 方法一循环
n = 33
left = 0
right = len(lst) - 1
count = 1

while left <= right:
    middle = (left + right) // 2
    if n < lst[middle]:
        right = middle - 1
    elif n > lst[middle]:
        left = middle + 1
    else:
        print("%s在列表中的下标是%d查找次数%d" % (n, middle, count))
        break
    count += 1
else:
    print("%s不在列表lst中" % n)
# 方法二尾递归
def binary_search(n,left=0, right=len(lst)-1, count1=1):
    middle = (left + right) // 2
    # count1 += 1
    if left <= right:
        if n < lst[middle]:
            right = middle - 1
        elif n > lst[middle]:
            left = middle + 1
        else:
            return "%s在列表中的下标是%d查找次数%d" % (n, middle, count1)
        return binary_search(n,left, right, count1+1)
    return "%s不在列表lst中" % n


res = binary_search(44)
print(res)
# 方法三切片+尾递归
def binary_search(n, lst):
    left = 0
    right = len(lst) - 1
    if left > right:
        return "%s不在列表lst中" % n
    middle = (left + right) // 2
    if n < lst[middle]:
        lst = lst[:middle]
    elif n > lst[middle]:
        lst = lst[middle+1:]
    else:
        return "%s在列表中" % n
    return binary_search(n, lst)


res = binary_search(11, lst)
print(res)