gpt4 book ai didi

python - QuickSort 返回正确的值,但没有原位排序

转载 作者:太空宇宙 更新时间:2023-11-04 01:26:12 25 4
gpt4 key购买 nike

我很难理解为什么我的 QuickSort 返回正确排序的值,但生成的数组排序不正确。

def qSort(array):
n = len(array)
if (n == 1 or n ==0):
return array
p_index = partition(array)
p_value = array[p_index]
return(qSort(array[0:p_index]) + [p_value] + qSort(array[p_index+1:n]))

def partition(array):
pivot = array[0]
i = 1
for j in xrange(1,len(array)):
print j
if array[j] < pivot:
tmp = array[j]
array[j] = array[i]
array[i]=tmp
i += 1
tmp = array[i-1]
array[i-1] = pivot
array[0] = tmp
return i-1

这是一些示例输出:

>>> q = [5,4,3,2,1]
>>> qSort(q)
[1, 2, 3, 4, 5]
>>> q
[1, 4, 3, 2, 5]

提前致谢!

最佳答案

在 Python 中,切片和组合列表会创建新列表。如果您希望递归调用就地对单个列表进行操作,请将列表和边界传递到调用中,并且不要从函数返回任何内容。像这样的东西:

def qsort(array, low, high):
if high-low < 2:
return

# Choose pivot, do partition within bounds

if partition > low:
qsort(array, low, partition)
if partition < high:
qsort(array, partition+1, high)

然后只需调用 qsort(a, 0, len(a)) 对数组进行排序。

关于python - QuickSort 返回正确的值,但没有原位排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17760166/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com