def hanoi(n, a, b, c):
"""
:param n: 盘子数量
:param a: a柱子
:param b: b柱子
:param c: c柱子
:return:
"""
if n > 0:
hanoi(n - 1, a, c, b) # 把n-1个盘子从A经过C移动到B
print('移动 %s 到 %s ' % (a, c)) # 把第n个盘子从A移动到C
hanoi(n - 1, b, a, c) # 把n-1个盘子从B经过A移动到C
查找
在数列中查找值的下标,列表的index()是顺序查找
顺序查找
def linear_search1(val, li):
"""
顺序查找
时间复杂度:O(n)
:param val:
:param li:
:return:
"""
for i in range(len(li)):
if li[i] == val:
return i
return None
def linear_search2(val, li):
for ind, v in enumerate(li):
if v == val:
return ind
return None
折半查找
折半查找的条件是数列要排好序
def binary_search(li, val):
"""
折半查找
时间复杂度:O(logn)
:param li: 排序好的数列
:param val: 要查找的值
:return:下标
"""
right = len(li) - 1
left = 0
while left <= right: # 候选区有值
mid = (left + right) // 2
if li[mid] == val:
return mid
elif li[mid] > val:
right = mid - 1
elif li[mid] < val:
left = mid + 1
return None
排序(low b版)
冒泡排序
def bubble_sort(li):
"""
冒泡排序
时间复杂度:O(n**2)
左右相互交换
一趟排序完成后有序区增加一个数,无序区减少一个数
:param li: 数列
:return:
"""
for i in range(len(li) - 1): # 第i趟
for j in range(len(li) - i - 1): # 下标
if li[j] > li[j + 1]:
li[j], li[j + 1] = li[j + 1], li[j]
改进冒泡排序思路:如果某次循环未发生交换,则认为已经排序完成
def new_bubble_sort(li):
"""
改进冒泡排序
某一趟如果不发生换位,则退出
:param li:
:return:
"""
for i in range(len(li) - 1): # 第i趟
exchange = False
for j in range(len(li) - i - 1): # 下标
if li[j] > li[j + 1]:
li[j], li[j + 1] = li[j + 1], li[j]
exchange = True
if not exchange:
return
选择排序
def select_sort(li):
"""
选择排序
从无序区拿出一个最小值放到有序区
默认第一个数为有序区
时间复杂度:O(n**2)
:param li:
:return:
"""
for i in range(len(li) - 1): # 最后一个数已经排好
min_location = i # i为无序区的最后一个值
for j in range(i + 1, len(li)): # 遍历无序区找最小值
if li[j] < li[min_location]:
min_location = j
li[i], li[min_location] = li[min_location], li[i]
插入排序
def insert_sort(li):
"""
插入排序
默认列表最右边为有序区
从无序区拿一个根据大小放到有序区
时间复杂度:O(n**2)
:param li:
:return:
"""
for i in range(1, len(li)): # i为无序区的下标
tmp = li[i]
j = i - 1 # 有序区下标
while j >= 0 and li[j] > tmp:
li[j + 1] = li[j]
j -= 1
li[j + 1] = tmp