快速排序递归性

Question

我正在尝试用python编写一个快速排序函数，但是在实现它时遇到了问题。我理解这个逻辑，但是我从来没有写过递归函数。你知道吗

我查阅了YouTube教程，但是它们使用的逻辑常常与我的逻辑不同。你知道吗

由于他们有几种方法做一个快速排序，我会张贴我的逻辑。 我的逻辑如下：

1. 数据透视是列表中随机选择的项
2. 轴将移动到列表中最右侧的位置。你知道吗
3. 然后将列表中的每个项目与透视图进行比较，以查看其是否大于透视图。你知道吗
4. 第一个比轴大的项目被指定为FirstBigNumber。你知道吗
5. 然后再次遍历该列表。列表中第一个小于pivot swaps位置的项，其FirstBigNumber为swaped=True
6. 然后找到一个新的FirstBigNumber
7. 重复步骤4、5、6，直到到达枢轴。你知道吗
8. 用FirstBigNumber交换数据透视。你知道吗
9. 应该对列表进行排序。你知道吗

我的代码：

import random
List=[3,5,1,7,2,8]
pivot_pos=0
def getpivot(List):
    #Get pivot position
    pivot_pos=random.randint(0,len(List)-1)
    return pivot_pos

def quicksort(List,pivot_pos):
    #Calling Get Pivot function
    getpivot(List)
    print(List)
    #Obtain pivot
    pivot=List[pivot_pos]
    print("Pivot is ",pivot)
    #Swap pivot to right of list
    List[len(List)-1],List[pivot_pos]=List[pivot_pos],List[len(List)-1]
    Swapped=True
    print(List)
    #Loop through List
    for j in range(0,len(List)-1):
        print("Checking if",List[j],"is bigger than",pivot)
        #Marks first num larger than
        if List[j]>pivot and Swapped==True:
            #FirstBigNum stores the index of the First number bigger than pivot
            FirstBigNum=List[j]
            IndexOfBigNum=j
            print("BigNum is",FirstBigNum)
            #This new Big number has not been swapped
            Swapped=False
        for i in range(0,len(List)-1):
            if List[i]<pivot:
                    #Swap the index of smaller num with first big num
                    print("Swapped",List[i]," with ",List[IndexOfBigNum])
                    List[IndexOfBigNum],List[i]=List[i],List[IndexOfBigNum]
                    print(List)
                    Swapped=True
            elif List[i]<pivot:
                print("Pivot is bigger than",List[i])
                #If Value greater than pivot
                pass
            elif i == (len(List)-1):
                #We have reached the end of the List
                #So we need to swap the pivot with the FirstBigNum
                List[FirstBigNum],List[i]==List[i],List[FirstBigNum]
                print("Here")
                print(List)
            else:
                #Is equal to pivot
                pass

getpivot(List)
quicksort(List,pivot_pos)

我收到的输出是：

[5, 8, 7, 2, 1, 3] 

我应该得到的结果是：

[1, 2, 3, 5, 7, 8]   

Answer 1

下面是一个使用递归和Lomuto分区的快速排序的标准实现。我包含了一个随机列表的主驱动程序，以便您可以测试它：

import random


def quick_sort(a, l=0, r=None):
    # Recusrion requires a Base Case
    if r is None :
        r = len(a) - 1
    if l >= r :
        return 0
    # If the Base Case is not encountered then proceed to partion
    s = lomuto_partition(a, l, r)
    # call quicksort recursively
    quick_sort(a, l, s-1)
    quick_sort(a, s+1, r)
    return a


def lomuto_partition(a, l, r):
    p = a[l]
    s = l
    for i in range(l+1, r+1) :
        if a[i] < p :
            s += 1
            a[s], a[i] = a[i], a[s]
    a[l], a[s] = a[s], a[l]
    return s


def random_seq(n=10, lo=0, hi=100):
    seq = []
    for i in range(n):
        seq.append(random.randint(lo, hi))
    return seq


if __name__ == '__main__' :
    n = 16
    print('n:', n)

    a = random_seq(n)
    print("Unsorted Random List: ", a)

我希望这有帮助