嘿，这个问题问到点子上了——其实有两种常见的partition实现可以做到仅n-1次比较，我结合你给出的[1,2,3,4,5,6,7,8]（pivot选8）的例子给你拆解清楚：

1. Hoare分区算法（Hoare's Partition Scheme） #

Hoare的分区思路是从数组两端同时向中间扫描，刚好能避免常规实现里的那一次冗余比较。拿你的例子来说：

• 左指针从数组开头（索引0）出发，找大于等于pivot（8）的元素；右指针从倒数第二个元素（索引6，也就是7的位置）出发，找小于等于pivot的元素
• 左指针会依次做7次比较：1<8、2<8...7<8，直到触碰到pivot的位置（索引7）
• 这时右指针的位置是6，7<8，不需要移动，直接判断左指针已经超过右指针，扫描终止
• 整个过程刚好7次比较，也就是n-1（n=8）次

核心原因是：Hoare算法的终止条件是左右指针相遇或交叉，这个判断是和元素比较整合在一起的，不需要额外做一次“检查索引是否交叉”的冗余操作，自然少了一次比较。

2. 优化版Lomuto分区算法 #

如果你更习惯用单指针遍历的Lomuto风格，也能通过小调整把比较次数降到n-1次：
常规的Lomuto实现会把pivot也纳入遍历范围，或者在循环结束后多一次判断，但优化后我们可以直接跳过pivot，只遍历前n-1个元素：

def optimized_lomuto_partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    # 只遍历前n-1个元素（从low到high-1，共high-low个元素）
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    # 最后交换pivot到正确位置
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i+1

在你的例子里，这个函数会遍历1到7这7个元素，每个和8做一次比较，总共7次，完全没有额外的比较操作，刚好是n-1次。

为啥常规实现会多一次比较？ #

常规的简单实现（比如基础版Lomuto或者粗糙的双指针），要么会在遍历完所有元素后额外做一次i < j的判断，要么会把pivot和自己做一次比较，这就多出来那第n次比较。而上面两种优化实现，要么通过两端扫描的逻辑避免了冗余判断，要么直接跳过了pivot的自我比较，所以能把比较次数控制在n-1次。

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