从左边开始选出一个数，然后从最右边的数依次与之比较，小于选出的数就将右边那个数放置到选出的数原来的位置，如果真的有右边的数小于选出的数，那么放置完后就不在是拿右边的数与之比较了，而是拿左边的数，就这样每次改变都要换边，第一趟就能把选出的数放置相应的位置
最好情况下，快排时间复杂度为O(nlogn)，冒泡时间复杂度为O(n)
一般情况下，快排时间复杂度为O(nlogn)，冒泡时间复杂度为O(n^2)
最坏情况下，快排时间复杂度为O(n^2),冒泡时间复杂度为O(n^2)

import random
def quick(list, left, right):
    if left < right:
        mid = partion(list, left, right)
        quick(list, left, mid-1)
        quick(list, mid+1, right)


def partion(list, left, right):
    tmp = list[left] #选出的数，把他拿出来，也就是tmp
    while left < right:
        while left < right and list[right] >= tmp: #在右边的数大于选出的数情况下
            right -= 1 #光标左移
        list[left] = list[right] #右边的数放置到选出数的原来位置上
        while left < right and list[left] <= tmp: #在左边的数小于选出的数情况下
            left += 1 #光标右移
        list[right] = list[left] #左边比较的数放置到右边的位置，右边的位置原来放到选出数的位置，所以这个位置是空的
    list[left] = tmp #将选出的数放到改变后的位置
    return left 


aa = list(range(10))
random.shuffle(aa)
print(aa)
quick(aa, 0, len(aa)-1)
print(aa)