关于Hoare原始分区算法：是否需将基准元素交换至正确位置？

是的，Hoare的原始快速排序分区方法确实需要将基准元素交换到它的最终正确位置，这是保证算法终止性的关键步骤。

具体来说：

• Hoare的原始实现中，基准元素通常被选在数组的起始位置。分区过程通过左右指针相向移动，交换逆序元素，直到指针相遇，确定分割点。
• 分区结束后，必须将初始位置的基准元素与分割点附近的子区间元素交换，让基准落到其排序后的最终位置。
• 完成交换后，后续的递归排序会排除这个已经归位的基准元素，只对基准左右两侧的子数组进行排序——这一步是避免无限递归、确保算法终止的核心要求。

你在维基百科中看到的现代变体，很多会通过调整循环条件（比如使用do...while而非repeat...until）、修改比较逻辑（用>=/<=替代>/<）来简化实现，但这些变体本质上是对原始方法的优化或调整，原始Hoare分区的核心逻辑里，基准元素归位的步骤是不可或缺的。

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