我正在尝试用python实现快速排序:
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
根据我的assert语句,我知道我的分区算法工作得很好。你知道吗
但是,我的sort函数返回错误的结果。这段代码打印出来
[4, 1, 3, 2, 4, 3, 5, 54]
要排序的递归调用的边界应该是什么?我的目标是将子列表划分到pivot的左侧,并将子列表划分到pivot的右侧,两者都不包括pivot本身。你知道吗
切片复制列表的一部分,因此在递归调用中,不修改原始列表。因此,只有第一个
partition
修改列表。你知道吗Python中一些已知的好的排序,带有可选的Cython,包括Quicksort。顺便说一句,查看性能比较;您可能会发现快速排序不如内置的Timsort有吸引力: http://stromberg.dnsalias.org/~strombrg/sort-comparison/
相关问题 更多 >
编程相关推荐