在python中以最后一个元素为轴实现QuickSort

克里斯

我似乎无法正确完成此操作。我在下面粘贴了我的代码。使用print语句,我认为正在发生的事情是第一遍的结果是作为答案返回的结果,尽管所有递归步骤都通过print显示了输出,表明它们正在按预期方式工作,但结果似乎没有保存?我试图就地执行此操作,但只是修改了array [],但是我觉得这里有些误解。任何帮助表示赞赏。

键盘:http//codepad.org/jVMbbJTq

码:

def quicksort(array):
    if len(array) >1:
        print "enter array", array
        pivot = len(array) - 1
        print "pivot", array[pivot]
        x = 0
        while x < pivot:
            if array[x]>array[pivot]:
                piv = array[pivot]
                xval = array[x]
                array[x] = array[pivot-1]
                array[pivot] = xval
                array[pivot-1] = piv
        #        temp = array[x]
         #       array[x] = array[pivot]
         #       array[pivot] = temp
               # array.append(array.pop(x))
                pivot -= 1
            else:
                x += 1
        print "pre recur split array", array
        print "left", array[:pivot]
        print "right", array[pivot+1:]
        quicksort(array[:pivot])
        quicksort(array[pivot+1:])
        print "post recur split array", array
    return array
test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
#test = [21, 4, 1, 3]
print quicksort(test)
print "answer", test
布莱克金

我不确定这是否是代码唯一问题,但是您遇到的一个大问题是您的递归不会做任何有用的事情。也就是说,这两行对您没有帮助:

    quicksort(array[:pivot])
    quicksort(array[pivot+1:])

他们不执行任何操作的原因是您执行的切片将数据从输入列表复制array到新列表中。然后,递归调用尝试对复制的列表进行排序。递归排序根本不会更改原始列表,因此,如果忽略它们的返回值,则调用代码中的任何内容都不会改变。

有几种方法可以解决此问题。一个简单(但效率低下)的解决方案是将每个递归调用返回的值分配回原始列表的一部分:

    array[:pivot] = quicksort(array[:pivot])
    array[pivot+1:] = quicksort(array[pivot+1:])

但是,如果要执行类似的操作,则在代码前面的分区步骤中使用临时列表可能会使所有内容更容易理解(如果您打算在此期间复制所有数据,则无需进行就地分区递归)。

这是一个非常快速和肮脏的快速排序,它可以将内容复制一堆(因此效率不高):

def quicksort(array):
    if len(array) <= 1:
        return array
    pivot_val = array[-1]
    lower = [x for x in array if x < pivot_val]
    upper = [x for x in array if x > pivot_val]
    pivot_count = array.count(pivot)
    return quicksort(lower) + [pivot_val]*pivot_count + quicksort(upper)

另一种更有效的方法是避免制作数据的任何副本(这意味着不进行切片)。只需对所有内容进行排序,包括递归部分。为此,您需要能够在递归调用中传递额外的参数,以指定需要排序的索引范围。幸运的是,在Python中向函数添加可选参数很容易(另一个选择是拥有一个单独的帮助函数来处理所有递归)。

与上面的简单修补程序相比,这涉及到对代码的更多更改,因为您不能再len(array)用作应在何处找到枢轴(或告诉您何时完成递归)的指南。这是一个快速尝试,但是我可能需要调试一个错误或其他一些错误:

def quicksort(array, low=0, high=None):    # add optional arguments
    if high == None:
        high = len(array) - 1              # set high if it got the default
    if high - low > 0:
        pivot = high                       # use high and low to set up pivot and x
        x = low
        while x < pivot:
            if array[x]>array[pivot]:      # this part stays the same
                piv = array[pivot]
                xval = array[x]
                array[x] = array[pivot-1]
                array[pivot] = xval
                array[pivot-1] = piv
                pivot -= 1
            else:
                x += 1
        quicksort(array, low, pivot-1)     # pass on new high and low values
        quicksort(array, pivot+1, high)
    return array                           # you probably don't need this line any more

如果您采用这种就地方法,则可能希望摆脱return array该功能一部分。在适当位置运行的Python函数的标准是返回None(如果没有任何return语句,则会发生这种情况)。您将熟悉许多这样的方法。例如,list.append不返回任何内容,也不返回list.sort(“官方”排序功能)。当修改传递给它们的列表时,标准库模块中的函数(例如)random.shuffle也会返回None

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

在numpy数组中沿轴获取最后一个元素

删除python中set的最后一个元素

Python:比较列表中的最后一个元素

Python将列表中的最后一个元素分组

使用Python中每个列表的最后一个元素

For循环仅迭代Python中的最后一个元素

OrderedDict中的最后一个元素

Java中的TreeMap实现仅返回最后一个元素

将静态元素设置为下拉列表中的最后一个元素?

比较集合中的元素并将其设置为该集合的最后一个元素

如何将零轴移动到python中的最后一个位置?

迭代Python列表中的连续元素,以使最后一个元素与第一个元素结合

将列表的元素作为最后一个元素插入到python列表中的列表中

红宝石数组的最后一个元素为nil

如何将页脚设置为所有网站中的最后一个元素

在Chrome中为最后一个合理的内联块元素添加了额外的空间

为数组中的每个元素找到最后一个较小或相等的数字?

减去ndarray的最后一个轴

在文件(Python)的每一行中查找最后一个元素(数字)

如何在Selenium Python中的同一个div中查找最后一个元素

如何在Python中以不同的方式对待列表中的最后一个元素?

在最后一个轴上将外部减法与元素明智减法相结合?

从C ++中的集合中删除最后一个元素

Python切片列表中的第一个和最后一个元素

在Python列表中查找元素的第一个和最后一个出现的最佳方法是什么?

Python-如何删除列表列表中的最后一个元素?

如何从python复制列表列表而没有每个列表中的最后一个元素

能够仅访问Python Unicode字典中列表的最后一个元素

如何在列表理解中修改Python列表的最后一个元素?