辅助函数(2)：使用合适的基准元选择算法获取基准元并据此对向量区间 [left, right) 进行分拆 template <typename T, typename CMP_T=std::less<T>> void partition(vector<T>& v, int left, int right, CMP_T cmp=CMP_T())

这个函数的作用是对一个向量区间进行分割，使得左边的元素都小于等于基准元，右边的元素都大于等于基准元。这个函数的实现需要用到基准元选择算法，因为选择不合适的基准元可能会导致分割效率很低。

以下是一个示例实现：

template <typename T, typename CMP_T=std::less<T>>
void partition(vector<T>& v, int left, int right, CMP_T cmp=CMP_T()) {
    // 选择基准元
    int mid = (left + right) / 2;
    if (cmp(v[mid], v[left]))
        swap(v[mid], v[left]);
    if (cmp(v[right - 1], v[mid]))
        swap(v[right - 1], v[mid]);
    if (cmp(v[mid], v[left]))
        swap(v[mid], v[left]);
    T pivot = v[mid];

    // 分割
    int i = left, j = right - 1;
    while (i <= j) {
        while (cmp(v[i], pivot))
            i++;
        while (cmp(pivot, v[j]))
            j--;
        if (i <= j) {
            swap(v[i], v[j]);
            i++;
            j--;
        }
    }
}

这个实现选择中间位置的元素作为基准元，先将其与左端点和右端点中的较小者交换，再将其与左端点和右端点中的较大者交换，最后再将其与左端点和右端点中的较小者交换，这样就能保证基准元在 [left, right) 区间中的位置比较中间。然后使用双指针法进行分割，将小于基准元的元素放到左边，大于基准元的元素放到右边。