stable_partition是一个函数模板present在C ++ STL算法的头文件。 我看，这是一种自适应算法时间复杂度为O（n * LOGN）和O（N）取决于一些factors.Can有人给我解释一下什么是那些因素，以及如何的时间复杂度取决于这些因素。谢谢！

stable_partition is a function template present in algorithm header file of c++ STL. I read that it is an adaptive algorithm and its time complexity is O(n*logn) or O(n) depending on some factors.Can someone explain me what are those factors and how the time complexity depends on those factors. Thank You !

推荐答案

这取决于有多少内存可用。

It depends on how much memory is available.

如果你有足够的内存，一种方式是简单地创建一个足够大的缓冲区，插入从前面的各要素和背部，并把它放回原来的完成时。这将需要O（n）的时间。

If you have enough memory, one way is to simply create a big enough buffer, insert the respective elements from the front and back and put it back into the original when done. This will take O(n) time.

如果没有足够的内存，这如果你想重新排列 - - 的前部和提到了为O（n log n）的就地方法（有可能是另一种方法为好）页 + 到后面，你多次发现在形式子阵++++ --- 和重新安排（稳定），以 --- ++++ （可以用3逆转完成 - 扭转整个子阵，那么负部分，则正部分）

If there isn't enough memory, this page mentions a O(n log n) in-place approach (there might be another approach as well) - if you want to rearrange - to the front and + to the back, you repeatedly find subarrays in the form ++++--- and rearrange it (stably) to ---++++ (which can be done with 3 reverses - reverse the whole subarray, then the negative part, then the positive part).

有足够的内存的物理检查可以简单地通过尝试分配内存，并检查故障进行。这样做的一个方法是使用新，它可以抛出一个则为std :: bad_alloc 或返回一个空指针，根据不同的版本中使用，如果它不能分配存储器

The physical checking for enough memory can simply be done by trying to allocate the memory and checking for failure. One way to do this is with a new, which can either throw an std::bad_alloc or return a null pointer, depending on the version used, if it fails to allocate the memory.