如何在線性時間內進行穩定的二進制值排序？

Question

讓我們假設我們有一個：

class Widget; 
std::vector<Widget>; 

而且我們有一個函數：

bool belongsToLeft(Widget w); 

我想按照這個謂詞的容器進行排序。到目前爲止，我通過這個算法。它從範圍的兩端進展。一旦找到一對同時屬於另一端的值，它就會交換它們。

template <typename TIterator, typename TPredicate> 
TIterator separate(TIterator begin, TIterator end, TPredicate belongsLeft) 
{ 
    while (true) 
    { 
     while (begin != end && belongsLeft(*begin)) 
      ++begin; 
     while (begin != end && !belongsLeft(*end)) 
      --end; 
     if (begin == end) 
      return begin; 
     std::swap(*begin, *end); 
    } 
} 

的問題是，這種算法並不穩定：

#include <vector> 
#include <iostream> 

int main() 
{ 
    std::vector<int> numbers = {6, 5, 4, 3, 2, 1}; 
    separate(numbers.begin(), numbers.end(), [](int x){return x%2 == 0;}); 

    for (int x : numbers) 
     std::cout << x << std::endl; 
    return 0; 
} 

輸出：

6 
2 
4 
3 
5 
1 

如何修改這個算法是穩定的，並保持線性的時間？

Answer 1

使用std::stable_partition與謂詞來單獨numbers成兩個部分，線性複雜

#include <algorithm> 

std::stable_partition(
    numbers.begin(), numbers.end(), 
    [](int x) { return x % 2 == 0; } // or belongsToLeft() 
);