Quicksorting cType數組數組

Question

我想在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 

Answer 1

您的外部while循環不適用於partseq。 Right和pivot的交換隻能在while循環之外進行一次。 return語句也應同時

同樣基於This link外面，我在first

第一內while循環運行，直到list[left] <= pivot和第二內作出小幅調整算法

• left開始而循環運行，直到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]