"""
运用左右指针法完成快速排序。
基本思路：
1.选出一个key,一般是最左边或是最右边的。
2.定义一个left和一个right指针，left从左向右走，right从右向左走。
3.在走的过程中，若right遇到小于key的数，则停下，left开始走，直到left遇到一个大于key的数时，将left和right的内容交换，
right再次开始走，如此进行下去，直到left和right最终相遇，此时将相遇点的内容与key交换即可。
4.此时key的左边都是小于key的数，key的右边都是大于key的数。
5.将key的做序列和有序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，
此时此部分已完成升序。
"""
import random #调入随机模块。
def two_pointers(lst): #创建一个能够对列表“lst”实施前4步的函数。
key=lst[0] #思路1：指定数组中最左边的数为目标key。
l,r=0,len(lst)-1 #思路2：设定l为左指针，r为右指针，分别对应数组的索引值。
while r>l: #思路3：当左右指针相遇时结束循环。
while lst[r]>key and r>l: #右指针先行，当右指针值大于key，且右指针没有与左指针相遇时。
r -= 1 #右指针往左走，当循环结束时，右指针值小于key。
while lst[l]<=key and r>l: #右指针停下后，左指针开始向右走，当左指针值小于等于key，且左指针没有与右指针相遇是。
l += 1 #左指针向右走，当循环结束时，左指针值大于key。
if r != l: #如果左右指针没有相遇。
lst[l],lst[r]=lst[r],lst[l] #左右指针内容互换。
else: #如果左右指针相遇。
lst[0],lst[l]=lst[l],lst[0] #相遇指针值与key内容互换。
#经过第一轮排序，此时得到的数组，以完成思路4的要求。接下来利用函数嵌套函数，完成“繁殖”。
if len(lst[:r])<=1 and len(lst[r+1:])<=1: #思路5：如果key左右两边的数组长度都小于1。
return lst[:] #那么返回值为整条数组。即完成。
elif len(lst[:r])>1 and len(lst[r+1:])<=1: #如果左边数组长度超过1，右边数组长度小于1。
return two_pointers(lst[:r])+lst[r:r+1]+lst[r+1:] #那么将左边数组扔进函数继续走思路12345，中间key和右边数组直接加入。
elif len(lst[:r])<=1 and len(lst[r+1:])>1: ##如果右边数组长度超过1，左边数组长度小于1。
return lst[:r]+lst[r:r+1]+two_pointers(lst[r+1:]) #那么将右边数组扔进函数继续走思路12345，中间key和左边数组直接加入。
else: #如果两边数组长度都大于1.
return two_pointers(lst[:r])+lst[r:r+1]+two_pointers(lst[r+1:]) #将左右两边的数组分别扔进函数走思路12345，中间用key连接。
lst=[]
for i in range(random.randint(10,20)): #创建一个随机数组，数值在0到10之间，个数在10到20之内。
lst.append(random.randint(0,10))
print(lst) #打印随机数组。
print(two_pointers(lst)) #调用函数进行快速排序，并打印出来。
print("done!") #你成功了吗？！
写在最后：解题思路是学习平台大佬的（通识），代码自己摸索敲的。希望可以对其他小白有用，另外请大神大佬们给我一些指点，帮助小白博采众长，快速成长！
