python 快排+动态交换优化

正常的代码，比较直观的：

a = list([4,2,1,7,4,9,6,5,0,3,8]);
print(a)

def quicksort(left,right) :

    if left>right:
        return
    # 当i变为left值，第一次结束递归的条件是在左边的，当只有一个数后，递归的left传入本身，
    # right传入i-1，此时left是等于right的，减一后肯定小于left，此时return 结束此递归函数。此条件是判断只剩下一个数排序结束的情况
    tmp=a[left]
    i=left
    j=right
    while i!=j :
        print(a[j],tmp)
        while (a[j]>=tmp) & (i<j):
            j-=1
        while (a[i]<=tmp) & (i<j):
            i+=1
        if i<j :
            t=a[i]
            a[i]=a[j]
            a[j]=t

    a[left]=a[i]
    a[i]=tmp

    quicksort(left,i-1)
    quicksort(i+1,right)
    # 此处return结束的是这个quicksort函数
    return

quicksort(0,len(a)-1)
print(a)

基本思想大家都知道吧，就是找到一个基准数后，从右边找小于基准数的，再从左边遍历，找大于基准数，然后把这两个找到的数交换，最后指针撞在一起的时候，指针位置的数和基准数交换。

这个思想是最直观的，但是今天见识动态交换的思想，就是在移动中做下处理，不用最后特地交换找的数，指针移动更快

def quicksort(l, r, arr):
    m = arr[l]
    i = l
    j = r
    while i < j:
        while (i<j and m <= arr[j]):
            j -= 1
        if i < j:
            # print(arr)
            arr[i] = arr[j]
            # print(arr)
            i += 1
        while (i<j and m >= arr[i]):
            i += 1
        if i < j:
            # print(arr)
            arr[j] = arr[i]
            j -= 1
            # print(arr)
    arr[i] = m
    # print(arr)
    if l < i-1: 
        quicksort(l, i-1, arr)
    if i+1 < r: 
        quicksort(i+1, r, arr)

arr = [6,1,2,7,9,3,4,5,10,8]
leng = len(arr)
quicksort(0, leng-1, arr)
print(arr)