算法移动数组元素

Question

我无法弄清楚这项任务的算法,也许你有一个想法？任务:将数组移动到前半部分的数组将是奇数行的所有元素和第二行的所有元素.最简单的选择是将元素移动到另一个数组,因为它可以使用temp变量？

Input data array  = {1,2,3,4,5,6,7,8}
output data array = {2,4,6,8,1,3,5,7}

Answer 1

这是家庭作业吗？如果没有,请使用std::stable_partition():

struct IsEven {
    template<class T>
    bool operator()(const T& v) const { return v % 2 == 0; }
};

int* arr = {1,2,3,4,5,6,7,8};
int* mid = std::stable_partition(arr, arr+8, IsEven());

如果是家庭作业,那么您的教师可能希望您编写算法.如果您不必像在输入序列中那样维护排序,那么您可以相当高效地执行此操作:

1. 找到第一该元素并不满足谓词(即,是奇数).
2. 发现最后那个元素确实满足谓词(即是连)
3. 交换这两个元素.
4. 重复,从刚刚找到的位置开始,直到两个位置相遇.
5. 两个位置相遇的点是分区的中间,偶数停止,奇数开始.

这大致是如何std::partition()运作的.如果你必须保持输入数组中的相对顺序,那么你仍然可以就地执行它,但是如果你使用临时缓冲区它会更快.将与谓词不匹配的元素复制到该缓冲区中,并将那些元素压缩到那些缓冲区中.最后按顺序返回数组末尾不匹配的元素.