快速排序
分而治之思想主要把解决一个大问题分为以下步骤解决
- 把大问题拆成许多小问题
- 分别解决小问题
- 把小问题答案组合起来就可以得到大问题的答案
输入输出
输入一个数组，输出一个有序数组
设计与实现
设计
- 数组中只有一个元素，直接返回这个元素
- 数组中有两个元素，比较两个元素大小即可
- 数组中有三个元素，我们取第一个进行作为基准值，让剩余的两个进行和基准值进行比较，找出小与基准值的数组和大于基准值得数组。
- 让后分别从按3的方法把小于刚才基准值的数组，和大于基准值的数组排序。
- 最终结果= [小于基准值] + [基准值] + [大于基准值]
实现
def quickSort(list):
if len(list) < 2:
return list
else:
baseValue = list[0] //any value in array
less = [item for item in list[1:] if item <= baseValue]
greater = [item for item in list[1:] if item > baseValue]
return quickSort(less) + [baseValue] + quickSort(greater)
print quickSort([1,2,7,3,2,4,5])
关键点
- 把问题拆成小块，分别解决
- 汇总答案，得出结果
