python 快排+动态交换优化

水深无声 2022-01-08 01:47 244阅读 0赞

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

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)

转载于:https://www.cnblogs.com/zhangmingzhao/p/8138205.html