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

Question

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

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

Answer 1

Quicksort 就地排序。这意味着您必须确保当您的分区例程找到您选择的枢轴的最终排序位置时，您修改（如果需要）列表就地。分区例程对于快速排序至关重要。我看到您使用 Python 构造，例如 list compositions，但在这样做时，您似乎忘记了快速排序的工作原理。 初学者 需要额外的 space 没关系，但你真的应该编写分区例程，将给定列表就地。

您的递归 quick_sort_helper() 函数也令人困惑。在非递归情况下它 returns 一个数组，而在递归情况下它 returns 什么都没有。 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]

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

How to get output in my quicksort algorithm

python

algorithm

quicksort