我很难理解为什么我的 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))
对数组进行排序。
我是一名优秀的程序员,十分优秀!