我正在尝试使用python实现快速排序算法我认为我已经正确地完成了这些步骤,但似乎我的代码有问题,每次我运行代码它都不能工作,请你能帮我找出我的代码的问题。
def quicksort(alist,first,last):
if first < last:
split = partition(alist,first,last)
quicksort(alist,first,split-1)
quicksort(alist,split+1,last)
def partition(arr,first,last):
pivot_val = arr[first]
rightmark = first +1
leftmark = last
done = False
while not done:
while leftmark <= rightmark and arr[leftmark] <= pivot_val:
leftmark +=1
while arr[rightmark] >= pivot_val and rightmark >= leftmark:
rightmark -=1
if rightmark < leftmark:
done = True
else:
tmp = arr[leftmark]
arr[leftmark] = arr[rightmark]
arr[rightmark] = tmp
tmp = arr[rightmark]
arr[rightmark] = arr[first]
arr[first] = tmp
return rightmark
lst = [22,54,33,11,87,76,1,3]
quicksort(lst,0,len(lst)-1)
print(lst)
输出如下所示:
[54, 22, 11, 33, 76, 87, 1, 3]
发布于 2018-05-31 07:02:25
是的,通常的实现将pivot作为最后一个值,而不是第一个值,但这是不相关的。然而,错误是对rightmark和leftmark的初始化。假设左标记位于'left‘,即小于,且右标记大于,则左标记应初始化为first+1,右标记应初始化为最后。
这不是quicksort的正常实现,它的分区函数简单地线性循环通过数组(除了pivot)。它巧妙地将左标记向右移动,直到第一个条目大于轴心,然后向左移动右标记,直到它的第一个条目小于轴心。然后它交换这两个值,直到它们交叉。这就是结束条件。
https://stackoverflow.com/questions/50611358
复制相似问题