算法——快速排序
分而治之(divide and conquer, D&C)：重要的递归式问题解决方法，包括两个步骤
1）找出基线条件，要尽可能简单
2）不断将问题分解（缩小规模），直到符合基线条件
快速排序(quick sort)：第一个重要的D&C算法
# divide_and_conquer.py 分而治之 def sum(li): # 递归方法求和 if len(li) == 1: # base case return li[0] else: # recursive case return li[0] + sum(li[1:]) def items(li): # 递归方法求元素数 if len(li) == 1: return 1 else: return 1 + items(li[1:]) def max(li, num=0): if len(li) == 0: # base case return num else: # recurvise case if num < li[0]: num = li[0] return max(li[1:], num) if __name__ == ‘__main__‘: li = [1, 4, 6, 8, 9] print(sum(li)) print(items(li)) print(max(li))
# quick_sort.py 快速排序 def quick_sort(arr): if len(arr) < 2: # 如果数组小于两个值，返回（已经无需排序） return arr else: pivot = arr[0] # pivot 基准值 less = [i for i in arr[1:] if i <= pivot] greater = [i for i in arr[1:] if i > pivot] return quick_sort(less) + [pivot] + quick_sort(greater) if __name__ == ‘__main__‘: li = [10, 5, 2, 3] print(quick_sort(li))
原文：https://www.cnblogs.com/noonjuan/p/10922390.html