Fork me on GitHub

算法图解3/4-递归和快排

递归函数

认识递归

递归指的是函数调用自己。编写递归函数,必须告诉它何时停止,每个递归函数包含两个部分:

  • 基线条件 base case
  • 递归条件 recursive case

递归条件指的是函数调用自己,而基线条件则指的是函数不再调用自己,从而避免形成无限循环

1
2
3
4
5
6
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

调用栈可能很长,将占用大量的内存。栈的两个操作:

  • 压入元素(插入)
  • 弹出元素(删除并读取)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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!

求阶乘

1
2
3
4
5
def factorial(n):
if n == 1: # 自减操作的终止条件
return 1
else:
return n * factorial(n-1) # 递归调用本身

求斐波那契数列

1,1,2,3,5,8,13,…最开始的两个值1和1,后面的数是前面两个数的和

1
2
3
4
5
6
7
def fibonacci(n):
if n == 1:
return 1
elif n== 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)

分而治之

分而治之的工作原理

  • 找出最简单的基线条件:基线条件很可能是空数组或只包含一个元素的数组
  • 确定如何缩小问题的规模,使其符合基线条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 列表求和: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:])) # 将第一个元素和后面所有元素中的最大值进行比较,递归调用

二分法查找的分而治之思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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)的策略。找到一个基准值,再找出比它大和比它小的值:

整个数组分成:

  • 一个由所有小于基准值的数字组成的子数组;无序
  • 基准值
  • 一个由所有大于基准值的数字组成的子数组;无序

对这两个子数组进行快速排序

1
2
3
4
5
6
7
8
9
# 递归:快排
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)$

最佳情况就是平均情况

本文标题:算法图解3/4-递归和快排

发布时间:2019年10月16日 - 13:10

原始链接:http://www.renpeter.cn/2019/10/16/%E7%AE%97%E6%B3%95%E5%9B%BE%E8%A7%A33-4-%E9%80%92%E5%BD%92%E5%92%8C%E5%BF%AB%E6%8E%92.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

Coffee or Tea