算法学习笔记–排序之快速排序
定义
快速排序使用了分而治之的策略。
使用分而治之解决问题的两个步骤？
找出停止条件，这种条件尽可能简单。不断将问题分解（或者说缩小规模），直到符合停止条件。
实现
def quick_sort(array):
if len(array) <
2:
return array
else:
pivot = array[
0]
print "pivot: ", pivot
less = [i
for i
in array[
1:]
if i <= pivot]
print "less: ", less
greater = [i
for i
in array[
1:]
if i > pivot]
print "greater: ", greater
return quick_sort(less) + [pivot] + quick_sort(greater)
if __name__ ==
'__main__':
list1 = [
4,
3,
2,
1, -
2,
3,
5,
3]
print list1
print quick_sort(list1)
运行结果
[
4,
3,
2,
1, -
2,
3,
5,
3]
[-
2,
1,
2,
3,
3,
3,
4,
5]
