需用户参与比较的场景下，哪种排序算法可最小化用户提问次数？

你需要的是带传递闭包检查的插入排序，它完全匹配你描述的最优、最坏提问次数要求，适配用户偏好的传递性规则：

为什么插入排序符合要求： #

• 最优情况（n-1次提问）：当用户的偏好恰好是线性顺序（比如新加入的水果总是当前最喜爱或最不喜爱的），插入排序每次只需1次提问就能确定新元素的位置（直接放在已排序序列的头部/尾部），总提问次数为n-1，与题目要求一致。
• 最坏情况（n(n-1)/2次提问）：当新元素的位置无法通过已有偏好推断（比如每次插入的元素都需要和已排序的所有元素逐一确认顺序），插入排序的总提问次数为1+2+...+(n-1) = n(n-1)/2（即所有元素对的数量），完全覆盖题目中的最坏场景。

核心实现逻辑： #

1. 维护一个已排序的水果列表，同时用一个二维结构记录所有已知的偏好关系及其传递闭包（比如isBetter[a][b]表示已确认a优于b）。
2. 遍历未排序的水果，每次取出一个目标水果x：
   • 与已排序列表中的元素依次比对，先检查传递闭包：如果能通过已有关系直接推断x和当前元素的顺序，跳过提问；
   • 若无法推断，向用户提问获取偏好结果，然后更新传递闭包（比如若用户确认x优于y，则所有已知优于x的元素都自动优于y，所有y优于的元素也自动被x优于）。
3. 根据确认的顺序将x插入到已排序列表的对应位置。

这种方式严格遵循“仅在必要时提问”的原则，完全最小化了向用户发起的提问次数。

内容的提问来源于stack exchange，提问作者Dogu Deniz Ugur