#coding=utf-8
# 快速排序
'''
快速排序算法的原理如下：
在待排序的元素任取一个元素作为基准(通常选第一个元素，但最的选择方法是从待排序元素中随机选取一个作为基准)，称为基准元素；
将待排序的元素进行分区，比基准元素大的元素放在它的右边，比其小的放在它的左边；
对左右两个分区重复以上步骤直到所有元素都是有序的。
'''
def part(li, left, right): # 列表，最左索引，最右索引
key = li[left] # 把第一个元素作为基准元素
print("1:key=%s, left=%s, right=%s, li=%s" % (key, left, right, li) )
while left < right: # 当最左小于最右
# 从右往左扫描，找到第一个比基准元素小的元素
while right > left and li[right] >= key:
right -= 1
# 找到这个元素li[right]后，放入li[left]
li[left] = li[right]
print("2.1:left=%s-right=%s-%s" % (left, right, li) )
# 从左往右扫描，找到第一个比基准元素大的元素
while left < right and li[left] <= key:
left += 1
# 找到这个元素li[left]后，放入li[right]
li[right] = li[left]
print("2.2:left=%s-right=%s-%s" % (left, right, li) )
# 基准元素归位
li[left] = key
print("3:key=%s, left=%s, li[%s]=%s, li=%s" % (key, left, left, li[left], li) )
return left # 返回当前基准元素的索引
def quick_sort(li, left, right):
if left < right: # 如果左索引<右索引
mid = part(li, left, right) # 调用part进行分区 返回一个索引赋给mid
quick_sort(li, left, mid - 1) # 基准元素左边的元素进行递归排序
quick_sort(li, mid + 1, right) # 基准元素右边的进行递归排序
import random
# range()函数中有一个参数，则从0开始。
# range()函数中有两个参数，则将第一个参数做为起始位，第二个参数为结束位
li = list(range(9))
#print(li)
# 将序列的所有元素随机排序
random.shuffle(li)
print("排序准备%s" % li)
quick_sort(li, 0, len(li) - 1)
print("排序结果%s" % li)
排序准备[6, 5, 7, 3, 1, 0, 8, 4, 2]
1:key=6, left=0, right=8, li=[6, 5, 7, 3, 1, 0, 8, 4, 2]
2.1:left=0-right=8-[2, 5, 7, 3, 1, 0, 8, 4, 2]
2.2:left=2-right=8-[2, 5, 7, 3, 1, 0, 8, 4, 7]
2.1:left=2-right=7-[2, 5, 4, 3, 1, 0, 8, 4, 7]
2.2:left=6-right=7-[2, 5, 4, 3, 1, 0, 8, 8, 7]
2.1:left=6-right=6-[2, 5, 4, 3, 1, 0, 8, 8, 7]
2.2:left=6-right=6-[2, 5, 4, 3, 1, 0, 8, 8, 7]
3:key=6, left=6, li[6]=6, li=[2, 5, 4, 3, 1, 0, 6, 8, 7]
1:key=2, left=0, right=5, li=[2, 5, 4, 3, 1, 0, 6, 8, 7]
2.1:left=0-right=5-[0, 5, 4, 3, 1, 0, 6, 8, 7]
2.2:left=1-right=5-[0, 5, 4, 3, 1, 5, 6, 8, 7]
2.1:left=1-right=4-[0, 1, 4, 3, 1, 5, 6, 8, 7]
2.2:left=2-right=4-[0, 1, 4, 3, 4, 5, 6, 8, 7]
2.1:left=2-right=2-[0, 1, 4, 3, 4, 5, 6, 8, 7]
2.2:left=2-right=2-[0, 1, 4, 3, 4, 5, 6, 8, 7]
3:key=2, left=2, li[2]=2, li=[0, 1, 2, 3, 4, 5, 6, 8, 7]
1:key=0, left=0, right=1, li=[0, 1, 2, 3, 4, 5, 6, 8, 7]
2.1:left=0-right=0-[0, 1, 2, 3, 4, 5, 6, 8, 7]
2.2:left=0-right=0-[0, 1, 2, 3, 4, 5, 6, 8, 7]
3:key=0, left=0, li[0]=0, li=[0, 1, 2, 3, 4, 5, 6, 8, 7]
1:key=3, left=3, right=5, li=[0, 1, 2, 3, 4, 5, 6, 8, 7]
2.1:left=3-right=3-[0, 1, 2, 3, 4, 5, 6, 8, 7]
2.2:left=3-right=3-[0, 1, 2, 3, 4, 5, 6, 8, 7]
3:key=3, left=3, li[3]=3, li=[0, 1, 2, 3, 4, 5, 6, 8, 7]
1:key=4, left=4, right=5, li=[0, 1, 2, 3, 4, 5, 6, 8, 7]
2.1:left=4-right=4-[0, 1, 2, 3, 4, 5, 6, 8, 7]
2.2:left=4-right=4-[0, 1, 2, 3, 4, 5, 6, 8, 7]
3:key=4, left=4, li[4]=4, li=[0, 1, 2, 3, 4, 5, 6, 8, 7]
1:key=8, left=7, right=8, li=[0, 1, 2, 3, 4, 5, 6, 8, 7]
2.1:left=7-right=8-[0, 1, 2, 3, 4, 5, 6, 7, 7]
2.2:left=8-right=8-[0, 1, 2, 3, 4, 5, 6, 7, 7]
3:key=8, left=8, li[8]=8, li=[0, 1, 2, 3, 4, 5, 6, 7, 8]
排序结果[0, 1, 2, 3, 4, 5, 6, 7, 8]