思路

代码

python版

Hoare 分区方法的基本原理：

• 在 Hoare 分区方法中，选择一个中心点 x，通常选择中间的元素作为分区元素（x = arr[(l + r) // 2]）。

• 接着，初始化两个指针 i 和 j。i 从左边界 l 开始向右移动，j 从右边界 r 开始向左移动。

• 指针 i 和 j 向中间移动并满足以下条件：i 继续移动直到找到一个不小于 x 的元素；j 继续移动直到找到一个不大于 x 的元素。

• 当两个指针满足 i < j 时，交换 arr[i] 和 arr[j]，然后继续上述过程。

• 当这两个指针相遇时 (i >= j)，分区过程结束。此时，j 是最后一个参与交换的位置，或者是两个指针相遇的位置。