C++转Python开发者求助：如何修复我的快速排序实现？

你说得没错，问题核心确实是Python的切片（比如list[0:last1]）会创建副本，而不是引用原列表的元素。你的partition和递归调用都是在副本上操作，原列表根本没被正确修改，自然输出结果不对。

既然你不想给quick_sort添加索引参数或用非递归写法，我们可以用内部辅助函数来封装索引范围的处理，既保持对外的函数签名简洁，又能实现原地排序。下面是修改后的完整代码，我会一步步解释关键改动：

修改后的代码 #

from typing import Sequence, MutableSequence

def find_if(list: Sequence, predicate, start=0, end=None):
    """Find first element in list[start:end] which predicate returns true"""
    if end is None:
        end = len(list)
    for i in range(start, end):
        if predicate(list[i]):
            return i
    return None

def find_if_not(list: Sequence, predicate, start=0, end=None):
    return find_if(list, lambda x : not predicate(x), start, end)

def partition(list: MutableSequence, predicate, low=0, high=None):
    """Reorder elements in list[low:high] such that all elements satisfying predicate come first.
    Return index of first element in the second group (relative to original list)"""
    if high is None:
        high = len(list)
    first = find_if_not(list, predicate, low, high)
    if first is None:
        return high  # All elements satisfy predicate, return high as split point
    for i in range(first + 1, high):
        if predicate(list[i]):
            list[i], list[first] = list[first], list[i]
            first += 1
    return first

def quick_sort(list: MutableSequence, key = lambda x : x):
    def helper(low, high):
        # Base case: if the sublist has 0 or 1 element, no need to sort
        if high - low <= 1:
            return
        pivot = list[low]
        # Partition elements smaller than pivot to the left
        last1 = partition(list, lambda x : key(x) < key(pivot), low, high)
        # Partition elements equal to pivot right after the smaller ones
        first2 = partition(list, lambda x : key(x) == key(pivot), last1, high)
        # Recursively sort the smaller and larger sublists
        helper(low, last1)
        helper(first2, high)
    
    # Start the recursive sort on the entire list
    helper(0, len(list))

if __name__ == '__main__':
    arr = [6, 4, 7, 2, 8, 1, 3, 5, 2, 10, 13, 124, 1, 7]
    result = sorted(arr)
    quick_sort(arr)
    print("My sorted array: ", arr)
    print("Corrected result: ", result)

关键改动说明 #

1. 扩展查找与分割函数的范围支持：

   • 给find_if、find_if_not和partition添加了start/low和end/high参数，默认处理整个列表，但也可以指定原列表的任意区间。
   • partition现在返回的是原列表的索引，而不是切片的局部索引，避免了索引偏移错误。

2. 内部辅助函数封装索引逻辑：

   • 在quick_sort内部定义了helper函数，它接受low和high参数（表示要排序的原列表区间[low, high)），负责实际的递归排序。
   • 对外的quick_sort函数仍然保持原有的签名，不需要额外的索引参数，完全符合你的要求。

3. 原地操作原列表：
   所有的分割和排序操作都是直接在原列表上进行，没有创建任何切片副本，修改会直接反映到原列表中。

运行修改后的代码，你会看到排序结果和sorted(arr)完全一致了。

内容的提问来源于stack exchange，提问作者Phạm Văn Thông