基础算法之快速排序(quick sort)
电子学会Python等级考试之3级学习内容：
快速排序(Quick Sort)是一种效率很高的排序算法，是对冒泡排序的一种改进排序算法。快速排序算法速度快，效率高，是处理大数据最快的排序算法之一
步骤为：
1. 挑选基准值：任意选取一个数据(通常选待排序列表中的第一个数)作为基准 数据（pivot）;选取基准值有数种具体方法, 选取方法对排序的时间性能有决定性影响。
2. 分割：重新排序数列，所有比基准值小的元素摆放在基准前面(左边)，
所有比基准值大的元素摆在基准后面（右边）。
此 时分割结束之后，对基准值的排序就已经完成;（第一轮排序完成).
3. 递归排序子序列：再按此方法对左右两部分的数据分别进行快速排序，整个排序过程可以递归进行，
递归结束的条件是直到被分割的数据只有一个或零个时，递归结束，列表排序完成。
动画演示如下:
下面以列表 [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] 进行升序排列为例，
从待排序列表中选取一个基准数据(通常选取第一个数据)。
array= [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
pivot=array[start] 将基准值选为数列的第一个元素
然后设置两个指针 left 和 right，用于指针所在位置的数值与基准值的比较，left 的right分别指向列表的起始数据和末尾数据。
left=start #开始指针
right=end #结束指针
2. 首先从右边开始, 将right指针的数据与基准数据比较，如果大于或等于基准值，则right往左移动，直到right指针的数据小于基准值.(基准值为10，21>10，right指针左移到36位置，36>10，继续左移，right移动到5时, 5<10，停止移动)
while array[right]>=mid_data and left<right: #如果大于基准值
right-=1 # 指针位置左移
当right指针的数据小于基准数据时，right指针停止移动，将right指针位置的数据赋值给指针left。
array[left]=array[right] #将5赋值给left
然后从左边开始,将left指针的数据与基准值比较，如果小于基准值，则left往右移动。
当游标left的数据大于或等于基准数据时，left指针停止移动.将left指针位置的数据赋值给指针right。(left指针移动到17时，17>10，停止移动. 并将17赋值给right，然后right 指针开始左移)
while array[left]<mid_data and left<right:
left +=1
array[right]=array[left]
3. right指针移动到7时，7<于10，停止移动，并将7赋值给left，然后left指针开始右移。array[right]=array[left]
4. left指针移动到50时，50>10，停止移动,并将50赋值给right指针，right指针开始左移。array[left]=array[right]
5. 当left与right相遇时，移动结束，将基准值(10)赋值给相遇的位置(array[left])，
array[left]=mid_data
此时第一轮排序完成，列表被基准数据分割成了两个子列表，左边小于基准值(10),右边大于基准值，基准值的位置就是排序完成时的位置。
6. 递归地对分割的两个子列表进行上面相同的操作。
以左表为例，取第一个数据5作为基准数据，设置两个游标left和right指向子表的起始和末尾，将游标right的数据与基准数据比较，如果大于或等于基准数据，则right往左移动。
左表中只有两个数据，经过一次移动，left和right就相等了，移动结束，左表排序完成。对右表也使用相同方法进行递归，这里就不再赘述了。
7. 继续进行多轮递归排序，每一轮当子表只有一个或零个数据时(left>=right)，递归结束。排序结果如下图。
完整程序如下:
def quick_sort(array,start,end):
if start>= end: #结束条件,如果开始指针>=结束指针,结束循环
return
mid_data=array[start] #设定基准值
left=start #开始指针
right=end #结束指针
while left <right: #开始指针小于结束指针时循环
while array[right]>=mid_data and left<right: #如果右边指针所在位置的值大于基准值时循环下面命令
right-=1 # 右指针左移
array[left]=array[right] #当下标right的数值小于基准值时，下标停止左移，并将下标所在的值赋值给左边，然后左边开始右移
while array[left]<mid_data and left<right:#如果左指针所在位置的值大于基准值时，循环下面命令
left +=1 # 左指针右移
array[right]=array[left] #当下标right的数值小于基准值时，下标停止右移，并将下标所在的值赋值给右边，然后右边开始左移
array[left]=mid_data #当结束循环时,将基准值赋值给相遇的位置，
quick_sort(array,start,left-1) #对左边的列表进行排序
quick_sort(array,left+1,end) #对右边的列表进行排序
array=[10,9,3,4,15,43,1,56]
quick_sort(array,0,len(array)-1)
print(array)