为什么我的quicksort实现的界限出错？

我想在Python中实现快速排序：为什么我的quicksort实现的界限出错？

def partition(ls): 
    if len(ls) == 0: 
    return 0 
    pivot = ls[0] 
    i = 0 
    j = 1 
    while j < len(ls): 
    if ls[j] <= pivot: 
     i += 1 
     temp = ls[i] 
     ls[i] = ls[j] 
     ls[j] = temp 
    j += 1 
    ls[0] = ls[i] 
    ls[i] = pivot 
    return i 

assert(partition([1,2]) == 0) 
assert(partition([3,2]) == 1) 
assert(partition([3,2,1,4,5]) == 2) 
assert(partition([]) == 0) 
assert(partition([45]) == 0) 

def sort(ls): 
    if len(ls) == 0: 
    return 
    pivotIndex = partition(ls) 
    sort(ls[0:pivotIndex]) 
    sort(ls[(pivotIndex + 1):len(ls)]) 

ls = [54,1,3,2,4,3,5,4] 
sort(ls) 
print ls

根据我的断言语句，我知道我的分区算法正常工作。

但是，我的排序函数返回错误的结果。这段代码打印

[4, 1, 3, 2, 4, 3, 5, 54]

什么应该是递归调用的边界排序？我的目标是将子列表分割到数据透视表的左侧，并将子列表划分到数据透视图的右侧，两者都不包括数据透视表本身。

来源

2012-06-23 John Hoffman

要求陌生人在您的代码中发现错误并不是富有成效的。那里有无数的quicksort实现。我建议单步执行代码，并将其行为与已知好的实现进行比较。 –

另外，你可以在你的代码中加入一些'print'来查看你的索引在做什么，这会让你弄清楚他们做错了什么。 – BrenBarn

您的assert语句只显示'partition'将主元素放置在正确的索引处，而不是分区正确。另外，在切片时（'ls [start：end]'）构造，你正在复制列表，这种错过了实现就地快速排序的要点。您应该将作为参数运行范围的开始和结束索引设置为sort（）。 – millimoose

sort(ls[0:pivotIndex]) 
sort(ls[(pivotIndex + 1):len(ls)])

切片复制列表的一部分，所以在递归调用中，您不会修改原始列表。因此只有第一个partition修改列表。

来源

2012-06-23 22:27:47

一些已知的好人在Python可选用Cython，其中包括快速排序。顺便说一下，检查性能比较;您可能会发现Quicksort不像内置Timsort那样有吸引力： http://stromberg.dnsalias.org/~strombrg/sort-comparison/

来源

2012-06-23 23:54:27 user1277476

为什么我的quicksort实现的界限出错？

回答

相关问题