Python实现快速排序
1、打开Python开发工具IDLE,新建‘快排.py’文件，并写代码如下：
def kuaipai(list1):
n = len(list1)
low = 0
high = n-1
mid = list1[low]
while low<high:
while low<high and list1[high]>=mid:
high-=1
list1[low]=list1[high]
while low<high and list1[low]<mid:
low+=1
list1[high]=list1[low]
list1[low]=mid
if __name__ == '__main__':
list1 = [8,10,6,7,9]
kuaipai(list1)
print (list1)
列表第一个值，作为基准，小于这个值，放到左边，大于放到右边，把这个值放到中间
2、F5运行程序，可以看到以这个值为中间，分成左右大小顺序
[7, 6, 8, 10, 9]
3、递归调要这个函数，以实现上一步分成左右分组继续排序，代码如下：
def kuaipai(list1,start,end):
low = start
high = end
mid = list1[low]
while low<high:
while low<high and list1[high]>=mid:
high-=1
list1[low]=list1[high]
while low<high and list1[low]<mid:
low+=1
list1[high]=list1[low]
list1[low]=mid
kuaipai(list1,start,low-1)
kuaipai(list1,low+1,end)
if __name__ == '__main__':
list1 = [8,7,6,9]
kuaipai(list1,0,len(list1)-1)
print (list1)
这样实现了左右两边再递归调用快排
4、F5运行程序，程序报错了，这是因为递归没有结束条件。
RecursionError: maximum recursion depth exceeded in comparison
5、继续改写代码，为递归找一个结束条件，结束条件就是已经排好序，排好序时左右移动的low和high重叠的一定实在一个端点。即一个一次也没有移动，一个移动到头。改写代码如下：
def kuaipai(list1,start,end):
if start>=end:
return
low = start
high = end
mid = list1[low]
while low<high:
while low<high and list1[high]>=mid:
high-=1
list1[low]=list1[high]
while low<high and list1[low]<mid:
low+=1
list1[high]=list1[low]
list1[low]=mid
kuaipai(list1,start,low-1)
kuaipai(list1,low+1,end)
if __name__ == '__main__':
list1 = [8,7,6,9]
kuaipai(list1,0,len(list1)-1)
print (list1)
6、F5运行程序，快速排序成功
[6, 7, 8, 9]
