我正在尝试找出快速排序算法。我尝试过不同的实现。我遇到的问题与枢轴元素的包含/排除有关。
考虑这三种实现。
此代码会导致 VS 代码出错,并且 VS 代码会停止。请注意,枢轴元素 (
ind
) 仅在 left
中包含一次(至少在我看来是这样),并且它不会单独添加到函数的最后一行中:
def quick_sort(arr):
if len(arr)<=1:
return arr
ind = arr[0]
left = [i for i in arr if i <= ind]
right = [i for i in arr if i > ind]
return quick_sort(left) + quick_sort(right)
如果我从
ind
中排除 left
(使用 <
而不是 <=
)并在最后一行添加 [ind]
,则它可以工作。但排序后的列表不会与原始列表有任何重复项:
numbers = [5, 2, 3, 2, 7]
print("Sum of numbers:", quick_sort(numbers))
def quick_sort(arr):
if len(arr)<=1:
return arr
ind = arr[0]
left = [i for i in arr if i < ind]
right = [i for i in arr if i > ind]
return quick_sort(left) + [ind] + quick_sort(right)
最后,这个实现可以很好地对所有值进行正确排序。但我不明白这个实现和第一个实现有什么区别。为什么第一个会导致错误,而这个却有效?然而,在这两种情况下,我们都只包含一次枢轴 (
ind
)?
numbers = [5, 2, 3, 2, 7]
print("Sum of numbers:", quick_sort(numbers))
def quick_sort(arr):
if len(arr)<=1:
return arr
ind = arr[0]
left = [i for i in arr if i < ind]
middle = [i for i in arr if i == ind]
right = [i for i in arr if i > ind]
return quick_sort(left) + middle + quick_sort(right)
我检查了之前关于这个主题的问答,但没有找到任何关于这个问题的内容。
left
获取给定列表中的all 值时(并且
right
保持为空),实现 #1 将遭受无限递归。在这种情况下,没有任何进展,递归调用将再次解决完全相同的问题,导致相同的重复递归调用......等等。例如,输入 [2, 1] 就会发生这种情况。
您已经正确识别了第二次实现的问题。如果主值有重复项,则会从结果中删除它们。第三次实现解决了这个问题。
第二个和第三个实现都解决了第一个实现的问题:保证递归调用将处理严格较短的列表,因为保证一个或所有主值不再是列表的成员它被传递给递归调用。
与您的问题无关,但快速排序通常作为“就地”算法实现,即在此过程中不创建新列表。相反,给定的列表是通过交换而改变的。请参阅有关快速排序的维基百科。