下面函数 f
实现了什么功能?
def f(nums):
if len(nums) <= 1:
return nums
p = nums[len(nums)//2]
left = [x for x in nums if x < p]
middle = [x for x in nums if x == p]
right = [x for x in nums if x > p]
return f(left) + middle + f(right)
如果你读以上代码有困难,不要紧,只要你搞懂了,你今天就会进步。
一般,刚接触编程的朋友,理解递归可能有些吃力。其实,对于编程多年的朋友可能平时也不太习惯使用递归。不过某些场景,使用递归会让代码更漂亮。上面函数f
就是一个例子。
理解递归,要把握两点:
就f
而言,递归基是下面两行代码:
if len(nums) <= 1:
return nums
它确保递归可以正常退出,从上而下去,再从下而上回,这里所谓的下
就是指递归基
。
递归方程确保问题规模逐渐接近递归基,也指问题规模从大变小的一个过程。就本f
而言,它的递归方程:
其中,
所以每递归一次,问题规模就会变小一点,直到满足递归基。
叨叨这么久,到底f
实现啥功能?
每次找出nums
列表中小于p
的区域、等于p
的区域、大于p
的右区域。左、右区域重复同样的f
操作。
所以这其实就是:快速排序,中间值作用相当于pivot
请看下面的例子:
r1 = f([3, 6, 8, 10, 3, 1, 2])
print(r1)
r2 = f([8, 7, 6, 5, 4, 3])
print(r2)
分别输出:
[1, 2, 3, 3, 6, 8, 10]
[3, 4, 5, 6, 7, 8]
以第一个例子演示图如下,
排序过程:
原创不易,欢迎三连支持