常见算法举例

1.抱着我的小鲤鱼的我

def xiaoliyu(n):
    if n == 0:
        print("我的小鲤鱼", end="")
    else:
        print("抱着", end="")
        xiaoliyu(n-1)
        print("的我", end="")
xiaoliyu(5)

2.汉诺塔

大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。

大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

64根柱子移动完毕之日，就是世界毁灭之时。

问题分解：

n个盘子时：
    1.把n-1个圆盘从A经过C移动到B
    2.把第n个圆盘从A移动到C
    3.把n-1个小圆盘从B经过A移动到C

def hanoi(n, A, B, C):
    if n > 0:
        hanoi(n-1, A, C, B)
        print("%s -> %s"%(A, C))
        hanoi(n - 1, B, A, C)

hanoi(8, 'A', 'B', 'C')

3.二分查找

从有序列表的候选区data[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。

def binarySearch(li, val, low, high):
    low = 0
    high = len(li) - 1
    while low <= high:
        mid = (low+high) // 2
        if li[mid] > val:
            high = mid - 1
        elif li[mid] < val:
            low = mid + 1
        else:
            return mid
    else:
        return -1

li = list(range(0, 1000, 2))
ret = binarySearch(li, 352, 0, len(li)-1)
print(ret)

4.冒泡排序

思路：列表每两个相邻的数，如果前边的比后边的大，那么交换这两个数
代码关键点：无序区，趟数
时间复杂度：O(n2)

def bubble_sort(li):
    for i in range(len(li)-1):
        # i 表示第几趟
        # 第i趟时，无序区：(0, len(li) - i]
        for j in range(0, len(li) - i - 1):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]

如果冒泡排序中执行一趟而没有交换，则列表已经是有序状态，可以直接结束算法。

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

5.选择排序

选择排序思路
    一趟遍历记录最小的数，放到第一个位置；
    再一趟遍历记录剩余列表中最小的数，继续放置；
    ...

问题是：怎么选出最小的数。
关键点：最小值的位置，无序区
时间复杂度：O(n2)

def select_sort(li):
    for i in range(len(li) - 1):
        # i 表示第几趟，也表示无序区开始的位置
        min_loc = i  # 最小数的位置
        for j in range(i + 1, len(li) - 1):
            if li[j] < li[min_loc]:
                min_loc = j
        if min_loc != i:
            li[i], li[min_loc] = li[min_loc], li[i]

import random
li = [random.randint(1,10000) for _ in range(100)]
print(li)
select_sort(li)
print(li)

6.插入排序

插入排序：
    列表被分为有序区和无序区两个部分。最初有序区只有一个元素
    每次从无序区中选择一个元素，插入到有序区的位置，直到无序区变空
    
关键点：
    摸到的牌
    手里的牌

时间复杂度：O(n2)
优化空间：应用二分查找来寻找插入点（并没有什么卵用）

def insert_sort(li):
    for i in range(1, len(li)):
        # i表示无序区第一张牌
        tmp = li[i]  # 摸到的第一张牌
        j = i - 1  # j 表示有序区最后位置
        while li[j] > tmp and j >= 0:
            # 循环终止条件：li[j]<tmp   j == -1
            li[j+1] = li[j]
            j -= 1
        li[j+1] = tmp

import random
li = [random.randint(1,10000) for _ in range(100)]
print(li)
insert_sort(li)
print(li)

7.快速排序

快速排序
特点：快
快排思路：
    取一个元素p（第一个元素），使元素p归位
    列表被p分成两部分。左边都比p小，右边都比p大
    递归完成排序
关键点：
    归位
    递归
时间复杂度：nlogn
最坏情况：n^2
解决方案：随机化

def partition(data, left, right):
    # ri = random.randint(left, right)
    # li[left], li[ri] = li[ri], li[left]  # 随机化
    tmp = data[left]
    while left < right:
        while left < right and data[right] >= tmp:
            right -= 1
        data[left] = data[right]
        while left < right and data[left] <= tmp:
            left += 1
        data[right] = data[left]
    data[left] = tmp
    return left

def quick_sort(data, left, right):
    if left < right:  # 至少2个元素
        mid = partition(data, left, right)
        quick_sort(data, left, mid-1)
        quick_sort(data, mid+1, right)

import random
li = [random.randint(1,10000) for _ in range(100)]
print(li)
quick_sort(li, 0, len(li)-1)
print(li)