Python 中的快速排序实现（分区期间包含与排除枢轴元素）

Question

我对编程和 Python 还很陌生。我目前正在尝试找出快速排序算法。我了解该算法的一般概念。我什至大部分都理解它的实现（好吧，不是真的）。到目前为止我遇到的问题与包含/排除枢轴元素有关。

考虑三种实现方式。

1. 此代码会导致 VS 代码出错，并且 VS 代码会停止。请注意，枢轴元素（ind）仅在左侧包含一次（至少对我来说是这样），我不会在最后一行代码中使用它

   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)    
   

2. 好的，如果我排除左侧的 ind （使用 < instead of <=) and add [ind] in the last line it works BUT the sorted list won't have any duplicates from the original list

   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)    
   

3. 最后，这个实现可以很好地排序，但我无法理解这个实现和#1 之间有什么区别。为什么 #1 会导致错误，而这个却可以工作，尽管在这两种情况下我们只包含一次主元 (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) 
   

我检查了之前的讨论并没有发现确切的这个问题。

Answer 1

当

left

 获取给定列表中的 

all 值时（并且 right

 保持为空），

实现 #1 将遭受无限递归。在这种情况下，没有任何进展，递归调用将再次解决完全相同的问题，导致相同的重复递归调用......等等。例如，输入 [2, 1] 就会发生这种情况。

您已经正确识别了第二次实现的问题。如果主值有重复项，则会从结果中删除它们。第三次实现解决了这个问题。

第二个和第三个实现都解决了第一个实现的问题：保证递归调用将处理严格较短的列表，因为保证一个或所有主值不再是列表的成员它被传递给递归调用。

与您的问题无关，但快速排序通常作为“就地”算法实现，即在此过程中不创建新列表。相反，给定的列表是通过交换而改变的。请参阅有关快速排序的维基百科。