写C++代码辅助函数(3) template <typename Iterator, typename CMP_T=std::less<decltype(*Iterator())>> Iterator choosepivot(Iterator left, Iterator right, CMP_T cmp=CMP_T());和辅助函数(4) template <typename Iterator, typename CMP_T=std::less<decltype(*Iterator())>> void partition(Iterator left, Iterator right, CMP_T cmp=CMP_T());
时间: 2023-06-17 18:02:50 浏览: 87
辅助函数(3)的作用是选择一个中心点(也就是 pivot)来分割序列,以便进行快速排序等算法。函数模板的定义如下:
```cpp
template <typename Iterator, typename CMP_T=std::less<decltype(*Iterator())>>
Iterator choosepivot(Iterator left, Iterator right, CMP_T cmp=CMP_T());
```
其中,`left` 和 `right` 分别表示序列的左右两个边界,`cmp` 是一个可调用对象,用于比较两个元素的大小。函数返回值是一个迭代器,指向选择出来的中心点。
以下是一个示例实现:
```cpp
template <typename Iterator, typename CMP_T>
Iterator choosepivot(Iterator left, Iterator right, CMP_T cmp)
{
Iterator mid = left + (right - left) / 2; // 取中间位置
if (cmp(*mid, *left)) // 保证 left <= mid
std::swap(left, mid);
if (cmp(*right, *left)) // 保证 left <= right
std::swap(left, right);
if (cmp(*mid, *right)) // 保证 mid >= right
std::swap(mid, right);
return mid;
}
```
辅助函数(4)的作用是将序列分为两部分,一部分比中心点小,一部分比中心点大,以便进行快速排序等算法。函数模板的定义如下:
```cpp
template <typename Iterator, typename CMP_T=std::less<decltype(*Iterator())>>
void partition(Iterator left, Iterator right, CMP_T cmp=CMP_T());
```
其中,`left` 和 `right` 分别表示序列的左右两个边界,`cmp` 是一个可调用对象,用于比较两个元素的大小。函数不返回值,但会将序列分成两部分。
以下是一个示例实现:
```cpp
template <typename Iterator, typename CMP_T>
void partition(Iterator left, Iterator right, CMP_T cmp)
{
Iterator pivot = choosepivot(left, right, cmp); // 选择中心点
std::swap(*pivot, *(right - 1)); // 将中心点放到末尾
pivot = right - 1;
Iterator i = left - 1;
for (Iterator j = left; j != pivot; ++j) {
if (cmp(*j, *pivot)) { // 如果 j 所指元素小于中心点
++i;
std::swap(*i, *j); // 将 j 所指元素和 i 所指元素交换
}
}
++i;
std::swap(*i, *pivot); // 将中心点放回到正确的位置
partition(left, i, cmp); // 递归处理左半部分
partition(i + 1, right, cmp); // 递归处理右半部分
}
```
阅读全文