算法图解3/4-递归和快排
递归函数
认识递归
递归指的是函数调用自己。编写递归函数，必须告诉它何时停止，每个递归函数包含两个部分：
- 基线条件
base case - 递归条件
recursive case
递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环
def look_key(box):
for item in box: # 遍历盒子中每个元素
if item.is_a_box(): # 如果是个盒子，递归调用函数
look_key(item)
elif item.is_a_key(): # 如果是key，直接结束
print("this is a key")调用栈 call stack
调用栈可能很长，将占用大量的内存。栈的两个操作：
- 压入元素（插入）
- 弹出元素（删除并读取）
def greet(name):
print ("hello, " + name + "!") # 1
greet2(name) # 执行该函数
print ("getting ready to say bye...")
bye()
def greet2(name):
print ("how are you, " + name + "?")
def bye():
print ("ok bye!")
greet("xiaoming")
# 结果
hello, xiaoming!
how are you, xiaoming?
getting ready to say bye...
ok bye!求阶乘
def factorial(n):
if n == 1: # 自减操作的终止条件
return 1
else:
return n * factorial(n-1) # 递归调用本身求斐波那契数列
1,1,2,3,5,8,13,…最开始的两个值1和1，后面的数是前面两个数的和
def fibonacci(n):
if n == 1:
return 1
elif n== 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)分而治之
分而治之的工作原理
- 找出最简单的基线条件：基线条件很可能是空数组或只包含一个元素的数组
- 确定如何缩小问题的规模，使其符合基线条件
# 列表求和：for遍历循环
def sum(arr): # arr=[2,3,4,5,6]
total = 0
for x in arr:
total += x
return total
# 分而治之:sum(arr) = 2+sum(arr[1:])=2+3+sum(arr[2:])......
def sum(a):
if len(a) == 0:
return 0
elif len(a) == 1:
return a[0]
else:
return a[0] + sum(a[1:]) # 用第一个数+后面所有数的和
# 递归方法：统计列表的元素个数
def count(arr):
if len(a) == 0:
return 0
elif len(a) == 1:
return 1
else:
return 1 + count(arr[1:]) # 第一个加上后面的所有元素个数
# 找出列表中最大的数
def bigger(a, b):
if a>= b:
return a
else:
return b
def maxArr(arr):
if len(arr) == 1: # 两种特殊情况
return arr[0]
elif len(arr) == 2:
return bigger(arr[0], arr[1])
else:
return bigger(arr[0], maxArr(list[1:])) # 将第一个元素和后面所有元素中的最大值进行比较，递归调用二分法查找的分而治之思想
def binary_search_impl(alist, item):
low = 0
high = len(alist) - 1
if low > high:
return None
else:
mid = (low + high) / 2
guess = alist[mid] # 取中间值
if guess == item:
return mid
elif guess > item: # 猜的太大了
high = mid - 1 # 将high值左移
return binary_search_impl(alist, item)
else:
low = mid + 1 # 猜的太小，low值右移
return binary_search_impl(alist, item)
def binary_search(alist, item):
return binary_search_impl(alist, item)快速排序
快排实现
快速排序采用的是分而治之（divide and conquer，D&C）的策略。找到一个基准值，再找出比它大和比它小的值：
整个数组分成：
- 一个由所有小于基准值的数字组成的子数组；无序
- 基准值
- 一个由所有大于基准值的数字组成的子数组；无序
对这两个子数组进行快速排序
# 递归：快排
def quicksort(arr):
if len(arr) < 2:
return arr
else:
pivot = arr[0] # 确定基准值
less = [i for i in arr[1:] if i < pivot] # 找出两个分区
greater = [i for i in arr[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater) # 对于两个分区再进行递归调用快排的平均运行时间O(n logn)，归并排序的运行时间总是O(n logn)
快排运行时间
最糟情况：O(n)*O(n)
最佳情况：O(nlogn)
最佳情况就是平均情况
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019-10-16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
