快速排序

分而治之思想主要把解决一个大问题分为以下步骤解决

• 把大问题拆成许多小问题
• 分别解决小问题
• 把小问题答案组合起来就可以得到大问题的答案

输入输出

输入一个数组，输出一个有序数组

设计与实现

设计

1. 数组中只有一个元素，直接返回这个元素
2. 数组中有两个元素，比较两个元素大小即可
3. 数组中有三个元素，我们取第一个进行作为基准值，让剩余的两个进行和基准值进行比较，找出小与基准值的数组和大于基准值得数组。
4. 让后分别从按3的方法把小于刚才基准值的数组，和大于基准值的数组排序。
5. 最终结果= [小于基准值] + [基准值] + [大于基准值]

实现

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])

关键点

• 把问题拆成小块，分别解决
• 汇总答案，得出结果