如何在快速排序算法中获得输出

2024-03-29 06:51:11 发布

您现在位置:Python中文网/ 问答频道 /正文

我尝试在我的快速排序算法中实现递归和列表理解。但我看不到任何输出。我可以得到帮助吗,我应该添加什么行来查看输出。我的逻辑似乎是正确的,反馈是赞赏的。你知道吗

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

下面的函数正在调用此函数。你知道吗

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  

Tags: helperforlenreturnifdefquicksort
1条回答
网友
1楼 · 发布于 2024-03-29 06:51:11

快速排序到位。这意味着您必须确保在分区例程找到所选轴心的最终排序位置时,您可以在适当的位置修改列表(如果需要)。分区例程对于快速排序至关重要。我看到您使用了类似于list compositions的Python构造,但这样做似乎忘记了快速排序的工作原理。对于初学者来说,需要额外的空间是可以的,但是您确实应该编写分区例程,将给定的列表分区到适当的位置。你知道吗

递归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]

相关问题 更多 >