c++ - 算法移动数组元素

Question

我想不出这个任务的算法，也许你有想法？任务:将数组移动到数组中，前半部分是奇数行的所有元素，后半部分是对行的所有元素。最简单的选择是将元素移动到另一个数组，因为它可以使一个使用临时变量？

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() 的大致工作方式。如果您确实必须保持输入数组中的相对顺序，那么您仍然可以就地进行，但如果您使用临时缓冲区，速度会更快。将与谓词不匹配的元素复制到该缓冲区中，然后将匹配的元素挤到适当的位置。最后将不匹配的元素按顺序带回数组的末尾。