如何在我的快速排序算法中獲得輸出

我正在嘗試在我的快速排序算法中實現遞歸和列表理解。但我無法看到任何輸出。我可以請求幫助，我應該添加哪些線路來查看輸出。我的邏輯似乎是正確的，反饋是讚賞。如何在我的快速排序算法中獲得輸出

def partition_list(A): 
    n = len(A) 
    m = A[n - 1] 
    #print m 
    A_left = [x for x in A if x <= m] 
    A_right = [x for x in A if x > m] 
    #if len(A_left) >= 2: 
    # return partition_list(A_left) 

    Anew = A_left + A_right 
    ind = Anew.index(m) 
    return Anew,ind

這個函數partition_list在下面的函數中被調用。

def quick_sort_helper(A): 
    if len(A) > 1: 
     Anew,m1 = partition_list(A) 
     print Anew 
     Aleft = Anew[0:m1] 
     Aright = Anew[m1 + 1:len(A)] 
     quick_sort_helper(Aleft) 
     print Aleft 
     quick_sort_helper(Aright) 
    else: 
     return A

來源

2017-02-25 jayant

快速排序到位。這意味着您必須確保在您的分區例程找到您選擇的數據透視表的最終排序位置時，請修改（如果需要）列表到位。分區例程對於快速分區非常重要。我看到你使用Python構造像列表組合，但這樣做，你似乎忘記了quicksort是如何工作的。沒關係初學者需要額外的空間，但你應該真的寫分區程序，將給定列表分區。

您的遞歸quick_sort_helper()函數也令人困惑。在非遞歸的情況下，它返回一個數組，而在遞歸情況下它不返回任何內容。 Python，（所謂的）鬆散地鍵入語言，並不阻止你這樣做。

我試圖改正你的代碼中的這些缺陷，同時保持你的選擇很大程度上完好，它似乎工作。當列表中有重複的元素時，它不起作用，並將其留作練習:-)。

#!/usr/bin/env python 


def partition_list(A, loIn, hiEx): 
    """ 
    Partitions the given list between given indexes such that the pivot is in its final sorted location. 
    Note: uses additional space. 
    :param A: the list of integers 
    :param loIn: low index, inclusive 
    :param hiEx: high index, exclusive 
    :return: index pi of pivot = (A[hiEx- 1]) in the sorted sequence, thus after the function returns, A[pi] = pivot and loIn <= pi < hiEx 
    """ 
    # print "partition call: loIn = %d, hiEx = %d" % (loIn, hiEx) 
    n = hiEx - loIn 
    pivot = A[hiEx - 1] # pivot is fixed, last element of the given array 
    # print "pivot: %d" % pivot 
    slice = A[loIn:hiEx] 
    A_left = [x for x in slice if x <= pivot] 
    A_right = [x for x in slice if x > pivot] 
    Anew = A_left + A_right 
    # print Anew 
    # copy it back, defeating the purpose of quicksort 
    for i in xrange(n): 
     A[loIn + i] = Anew[i] 
    index = A.index(pivot, loIn, hiEx) 
    # print "partition index: %d, element: %d" % (index, A[index]) 
    return index 


def quick_sort_helper(A, loIn, hiEx): 
    """ 
    Implements quicksort recursively. Call this as: quick_sort_helper(a, 0, len(a)) 
    :param A: the list to sort 
    :param loIn: low index, inclusive 
    :param hiEx: high index, exclusive 
    :return: nothing, sorts list in place. 
    """ 
    if hiEx - loIn > 1: 
     m1 = partition_list(A, loIn, hiEx) # A[m1] is in its final sorted position 
     quick_sort_helper(A, loIn, m1) 
     quick_sort_helper(A, m1 + 1, hiEx) 

a = [43, 2, 52, 23, 1, 0, 10, 7, 3] 
quick_sort_helper(a, 0, len(a)) 
print "sorted: ", a # prints: sorted: [0, 1, 2, 3, 7, 10, 23, 43, 52]

來源

2017-02-25 22:22:14

感謝您的建議和反饋。 – jayant

如何在我的快速排序算法中獲得輸出

回答

相關問題