一、快速排序
快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。
冒泡排序在每一轮中只把1个元素冒泡到数列的一端。而快速排序则在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分。
这种思路就叫作分治法。
在分治法的思想下，原数列在每一轮都被拆分成两部分，每一部分在下一轮又分别被拆分成两部分，直到不可再分为止。 每一轮的比较和交换，需要把数组中的全部元素都遍历一遍，时间复杂度是O(n)。这样的遍历一共需要多少轮呢﹖假如元素个数是n，那么平均情况下需要logn轮，因此快速排序算法总体的平均时间复杂度是O ( nlogn)。
基准元素，英文pivot，在分治过程中，以基准元素为中心，把其他元素移动到它的左右两边。
1、双边循环法。
2、单边循环法。
1、双边循环法
首先，选定基准元素pivot，并且设置两个指针left和right，指向数列的最左和最右两个元素。
第1次循环，从right指针开始，让指针所指向的元素和基准元素做比较。如果right>=pivot，则指针向左移动(-1);如果right<pivot，则right指针停止移动(stop)，切换到left指针。
在当前数列中，1<4，所以right直接停止移动，换到left指针，进行下一步行动。轮到left指针行动，让指针所指向的元素和基准元素做比较。如果left<=pivot，则指针向右移动(+1);如果left>pivot，则left指针停止移动(stop)。
由于left开始指向的是基准元素，判断肯定相等，所以left右移1位。
由于7>4，left指针在元素7的位置停下。这时，让left指针和right指针所指向的元素进行交换。
def partition(start,end,ll):
'''
比较交换过程
:param start: 开始索引
:param end: 结束索引
:param ll: 数列
:return: 左边索引
'''
#取第一个元素为基准元素，也可以随机
pirot=ll[start]
#左边元素索引
left=start
#右边元素索引
right=end
#循环
while left!=right:
#控制right指针比较，并左移
while left<right and ll[right]>=pirot:
right -=1
# 控制left指针比较，并右移
while left<right and ll[left]<=pirot:
left+=1
#交换left指针和right指针的元素
if left<right:
#交换
ll[left],ll[right]=ll[right],ll[left]
#pirot与left,right指针重合
ll[start]=ll[left]
ll[left]=pirot
return left
def quickSort(start,end,ll):
#递归结束
if start>=end:
return
#获取基准元素位置
pirot=partition(start,end,ll)
#根据基准元素，分成两部分递归排序
quickSort(start,pirot-1,ll)
quickSort(pirot+1,end,ll)
if __name__ == '__main__':
ll=[4,7,6,5,3,2,8,1]
print('排序前：')
print(ll)
#调用方法排序
quickSort(0,len(ll)-1,ll)
print('排序后：')
print(ll)
2、单边循环法
只从数组的一边对元素进行遍历和交换。
开始和双边循环法相似，首先选定基准元素pivot。同时，设置一个mark指针指向数列起始位置，这个mark指针代表小于基准元素的区域边界。接下来，从基准元素的下一个位置开始遍历数组。
如果遍历到的元素>基准元素，就继续往后遍历。
如果遍历到的元素<基准元素，则需要做两件事:
第一，把mark指针右移1位，因为小于pivot的区域边界增大了1;
第二，让最新遍历到的元素和mark指针所在位置的元素交换位置，因为最新遍历的元素归属于小于pivot的区域。
首先遍历到元素7，7>4，所以继续遍历。
遍历到的元素是3，3<4，所以mark指针右移1位。
随后，让元素3和mark指针所在位置的元素交换，因为元素3归属于小于pivot的区域。
def partitionSingle(start,end,ll):
# 取第一个元素为基准元素，也可以随机
pirot = ll[start]
# 标记索引
mark = start
for i in range(start+1,end+1):
#判断遍历的元素<基准元素
if ll[i]<pirot:
#右移1位
mark+=1
#交换
p=ll[mark]
ll[mark]=ll[i]
ll[i]=p
ll[start]=ll[mark]
ll[mark]=pirot
return mark
def quickSort(start,end,ll):
#递归结束
if start>=end:
return
#获取基准元素位置
pirot=partitionSingle(start,end,ll)
#根据基准元素，分成两部分递归排序
quickSort(start,pirot-1,ll)
quickSort(pirot+1,end,ll)很明显，partitionSingle方法只要一个循环就OK，的确比双边循环法简单多了。