快速排序cType数字数组

Question

我试图在Python3中的一个ctypes整数数组上实现两个排序方法，但似乎无法找到快速排序方法。我相信我的大部分代码是正确的，但我只是错过了一个愚蠢的语句。现在，当我试图打印这个返回的数组时，得到的只是一个“NoneType”对象。在

非常感谢。在

#Quicksort Algorithm
def quicksort(list):
    n = len(list)
    return recquick(list, 0, n-1)

#Recursive Quicksort Function
def recquick(list, first, last):
    #Base Case
    if first >= last:
        return
    else:
        #Save pivot value
        pivot = list[first]

        pos = partseq(list, first, last)

        #Repeat the process on the two subsequences
        recquick(list, first, pos-1)
        recquick(list, pos+1, last)

#Partitions subsequence using first key as pivot
def partseq(list, first, last):
    #Save pivot value
    pivot = list[first]

    #Find pivot position and move elements around the pivot
    left = first + 1
    right = last
    while left <= right:
        #Find the first key larger than the pivot
        while left < right and list[left] < pivot:
            left += 1

        #find the last key in the sequence that is smaller than the pivot
        while right >= left and list[right] >= pivot:
            right -= 1


        #Swap the two keys
        if left < right:
            tmp = list[left]
            list[left] = list[right]
            list[right] = tmp

        #Put the pivot in the proper position
        if right != first:
            list[first] = list[right]
            list[right] = pivot

        #Return index position of the pivot value
        return right

Answer 1

您的外部while循环在partseq中不正确。在while循环之外只应进行一次right和pivot的交换。返回语句也应该在while之外

同样基于This link，我对算法做了一些小的调整

• left从first开始
• 第一个内部while循环运行到list[left] <= pivot，第二个内部while循环运行到list[right] > pivot

#Quicksort Algorithm
def quicksort(list):
    n = len(list)
    return recquick(list, 0, n-1)

#Recursive Quicksort Function
def recquick(list, first, last):
    #Base Case
    if first >= last:
        return
    else:
        #Save pivot value
        pivot = list[first]

        pos = partseq(list, first, last)

        #Repeat the process on the two subsequences
        recquick(list, first, pos-1)
        recquick(list, pos+1, last)

#Partitions subsequence using first key as pivot
def partseq(list, first, last):
    #Find pivot position and move elements around the pivot
    pivot = list[first]

    left = first 
    right = last
    while left<right: 
        #Find the first key larger than the pivot

        while left < right and list[left] <= pivot:
            left += 1

        #find the last key in the sequence that is smaller than the pivot
        while right >= left and list[right] > pivot:
            right -= 1

        #Swap the two keys
        if left < right:
            tmp = list[left]
            list[left] = list[right]
            list[right] = tmp


    #Put the pivot in the proper position
    #right to left
    if right != first:
        list[first] = list[right]
        list[right] = pivot

    #Return index position of the pivot value
    return right

结果

>>> import try1
>>> a=[1,2,3,4,5,6,]
>>> try1.quicksort(a)
>>> a
[1, 2, 3, 4, 5, 6]
>>> a=[6,5,4,3,2,1,]
>>> try1.quicksort(a)
>>> a
[1, 2, 3, 4, 5, 6]
>>> a=[1]
>>> try1.quicksort(a)
>>> a
[1]
>>> a=[]
>>> try1.quicksort(a)
>>> a
[]
>>> a=[43,76,9,10,1,15,62,]
>>> try1.quicksort(a)
>>> a
[1, 9, 10, 15, 43, 62, 76]