基于双指针的至多两值数组排序函数故障排查求助

嘿，我来帮你搞定这个双指针排序的问题！首先咱们先明确任务背景：

出自R. Sedgewick《Introduction TO PROGRAMMING IN PYTHON An Interdisciplinary Approach》的Partitioning章节任务：对至多含两种不同值的数组排序，要求采用双指针法，维护左指针右侧、右指针左侧的元素不变性。

你提到自己写的quickSort2函数运行异常，怀疑是连续调用两个quickSort2的代码段有问题——其实问题大概率出在不必要的递归调用上：对于只有两种值的数组，根本不需要像标准快速排序那样递归处理左右子数组，一次双指针遍历就能完成排序，递归反而容易引入边界处理错误，打乱已经排好的元素。

双指针法的核心逻辑 #

咱们先把双指针的正确思路理清楚：

• 左指针left从数组头部出发，负责定位需要移到右侧的元素（比如我们把其中一种值放在左边，另一种放右边，左指针找不属于左侧值的元素）
• 右指针right从数组尾部出发，负责定位需要移到左侧的元素（找属于左侧值的元素）
• 只要left < right，就交换两个指针指向的元素，然后移动指针继续遍历
• 整个过程要维护不变性：left左侧全是目标值，right右侧全是另一种值，中间是待处理的元素

正确的实现代码 #

下面是符合要求的双指针排序函数，专门处理至多两种值的数组：

def sort_two_unique_values(arr):
    if len(arr) <= 1:
        return arr
    
    # 选取数组第一个元素作为左侧要保留的值（基准）
    target_val = arr[0]
    left = 0
    right = len(arr) - 1

    while left < right:
        # 左指针右移：跳过所有等于target_val的元素，直到找到需要移去右边的元素
        while left < right and arr[left] == target_val:
            left += 1
        # 右指针左移：跳过所有不等于target_val的元素，直到找到需要移去左边的元素
        while left < right and arr[right] != target_val:
            right -= 1
        # 交换两个元素，完成一次位置修正
        if left < right:
            arr[left], arr[right] = arr[right], arr[left]
    
    return arr

测试你的用例 #

用你给出的测试数组[5,5,4,5,5,5,5,4,5,5,4,5,4,4,4,4,4,4,5,5,4,5,4]运行这个函数，会得到正确的排序结果：所有4排在左侧，所有5排在右侧，完全符合预期。

为什么你的递归版本会出错？ #

标准快速排序的递归是为了处理多种不同值的数组，需要把数组分成小于基准、等于基准、大于基准的三部分，再递归处理左右。但咱们的任务是至多两种值，一次遍历就把数组分成了两部分，递归调用quickSort2处理左右子数组完全是多余的，甚至会因为边界判断错误（比如传入的left/right范围不对），导致已经排好的元素被再次交换，最终输出异常结果。

额外优化：自动适配两种值顺序 #

如果想让排序结果是从小到大（比如先4后5，而不是跟着第一个元素走），可以先找出数组中的最小值作为target_val，这样不管数组开头是什么值，都能得到升序结果：

def sort_two_values_asc(arr):
    if len(arr) <= 1:
        return arr
    
    min_val = min(arr)
    left = 0
    right = len(arr) - 1

    while left < right:
        while left < right and arr[left] == min_val:
            left += 1
        while left < right and arr[right] != min_val:
            right -= 1
        if left < right:
            arr[left], arr[right] = arr[right], arr[left]
    
    return arr

内容的提问来源于stack exchange，提问作者Blogger 2015