0

我正在尝试在 Python 3 中的整数 ctypes 数组上实现几个排序方法，但似乎无法弄清楚 Quicksort 方法。我相信我的大部分代码都是正确的，但我只是错过了一个愚蠢的陈述。现在，当我尝试打印返回的数组时，我得到的只是一个“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
4

1 回答 1

1

您的外部 while 循环在partseq. right 和 pivot 的交换应该只在 while 循环之外发生一次。return 语句也应该在 while 之外

同样基于这个链接，我对算法做了一些小的调整

  • 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]
于 2013-03-28T09:32:37.950 回答