软件环境:Python 3.7.0b4
工作原理:
# 4.2
def count(list):
if list == []:
return 0
return 1 + count(list[1:])
# 4.3
def max(list):
if len(list) == 2:
return list[0] if list[0] > list[1] else list[1]
sub_max = max(list[1:])
return list[0] if list[0] > sub_max else sub_max
4.4:二分查找的基线条件是数组只包含一个元素。如果要查找的值与这个元素相同,就找到了!否则说明它不在数组中。递归条件为 把数组分成两半,将其中一半丢弃,并对另一半执行二分查找。
def quicksort(array):
if len(array) < 2:
# 基线条件:为空或只包含一个元素的数组是“有序”的
return array
else:
# 递归条件
pivot = array[0]
# 由所有小于等于基准值的元素组成的子数组
less = [i for i in array[1:] if i <= pivot]
# 由所有大于基准值的元素组成的子数组
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([10, 5, 2, 3])) # 需排序的数组