这个算法可以用C++在O(N)时间内实现吗？

Question

我正在尝试在 C++ 中实现一个函数，该函数接受一个整数数组并返回相同的数组，排序如下（我通常是 C++ 和 CS 的初学者）

1. 所有奇数都在所有偶数之前
2. 奇数会保持原来的相对顺序
3. 偶数将以相反的顺序放置（相对于它们的原始顺序）。

所以如果 arr = [5, 2, 11, 7, 6, 4]，那么输出将是 [5, 11, 7, 4, 6, 2]。

是否可以在 O(n) 时间内按上面指定的方式对数组进行排序？如果是这样，提示会有所帮助，我会尝试自己弄清楚！

我能想到的最有效的解决方案是：

如果数组的第i个元素是偶数，则与数组中最后一个尚未交换的偶数元素交换

如果第 i 个元素是奇数，将它与数组中的第 [i-1] 个元素交换，直到第 [i-1] 个元素是奇数或到达数组的开头

移动到数组中的下一个元素

我已经将它编码并且它可以工作，但在最坏的情况下这似乎在 O(n^2) 时间内运行，因为基本上你必须遍历数组一次才能以正确的相对顺序获得均匀，然后去返回数组以在偶数之前获得所有赔率。

我很难想到 O(n) 实现，因为我想不出一种方法来确保所有元素都放在数组中的适当位置。基本上我能想到的所有算法都需要遍历数组，然后进行某种类型的排序。在这种情况下甚至可能使用 O(n) 算法吗？

当然你可以通过创建一个新数组并以适当的顺序复制元素然后返回新数组来做到这一点，但这没那么有趣，我想更好地理解实现高效算法

Answer 1

你可以为此使用标准库。

首先，执行 stable_partition，使用如果数字为奇数则返回 true 的谓词。这会将所有奇数值移到左侧，保留所有值的相对顺序。

该函数将迭代器返回到右侧的开头，因此此时您可以简单地reverse该数据。

stable_partition

是 O(N.logN) 最坏情况，

reverse

是 O(N)。所以这个解决方案在最坏的情况下是 O(N.logN) 时间复杂度和 O(1) 存储复杂度。

其实更可能是O(N)。该文档对于

stable_partition

应该如何实现有点不清楚，但确实表明该函数分配内存。在那种情况下，它是 O(N)，只有在分配失败时才回退到 O(N.logN) 行为。

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

inline bool is_odd(int value)
{
    return value % 2 != 0;
}

void show(const std::vector<int>& values)
{
    std::copy(values.begin(), values.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
}

int main()
{
    std::vector<int> values{ 5, 2, 11, 7, 6, 4 };
    show(values);

    // Partition the array, placing odd numbers first, then even numbers, preserving order
    auto it = std::stable_partition(values.begin(), values.end(), is_odd);
    show(values);

    // Reverse the even numbers
    std::reverse(it, values.end());
    show(values);
}