尝试使用python实现快速排序，但不起作用
尝试使用python实现快速排序，但不起作用
提问于 2018-05-31 02:32:15
我正在尝试使用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]回答 1
Stack Overflow用户
回答已采纳
发布于 2018-05-31 07:02:25
是的，通常的实现将pivot作为最后一个值，而不是第一个值，但这是不相关的。然而，错误是对rightmark和leftmark的初始化。假设左标记位于'left‘，即小于，且右标记大于，则左标记应初始化为first+1，右标记应初始化为最后。
这不是quicksort的正常实现，它的分区函数简单地线性循环通过数组(除了pivot)。它巧妙地将左标记向右移动，直到第一个条目大于轴心，然后向左移动右标记，直到它的第一个条目小于轴心。然后它交换这两个值，直到它们交叉。这就是结束条件。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50611358
复制相关文章
相似问题