排序分類矢量的子集

-1

我想弄清楚在多個條件下對數組進行排序的最佳方法。我想對一個數組進行排序，然後根據第一個條件排序該數組的一個子集。排序分類矢量的子集

例子：

說我們有數據：{ ("cat", 2), ("dog", 4), ("cat", 1), ("dog", 3) }

我們解決這首先根據串的字母順序：

{ ("cat", 2), ("cat", 1), ("dog", 4), ("dog", 3) }

然後我們兩個子集進行排序（集貓和狗的組合）：

{ ("cat", 1), ("cat", 2), ("dog", 3), ("dog", 4) }

另外，我使用具有下面的頭一個遞歸快速排序方法：

void quickSort(vector<Type*>, int left, int right)

其中左和右是邊界指數，通過該載體應進行排序。

我應該向排序方法本身添加代碼還是應該再次調用排序方法？

來源

2011-11-30 HJM

你應該自己思考一下。別人的幫助不會幫助你自己解決其他問題。我建議你不要使用StackOverflow來解決你的功課。 – Beginner

這不是一個家庭作業，自學，FYI。我一直在想。我已經知道了，我正在尋找我說的「最好」的方式。我正在尋找現在優化。 – HJM

通常，您需要自定義比較器進行排序。

struct Foo { 
    std::string name; 
    int count; 
    struct Less { 
    bool operator()(const Foo &lhs, const Foo &rhs) const { 
     if ((int c = lhs.name.compare(rhs.name)) != 0) 
     return c < 0; 
     return lhs.count < rhs.count; 
    } 
    }; 
}; 

std::vector<Foo> foos; 
// ... 
std::sort(foos.begin(), foos.end(), Foo::Less());

如果您不能只使用一個自定義操作符，則可以使用穩定的排序。

正如Mark指出的，std::sort是不是穩定排序。相反，您需要使用std::stable_sort。

您想按照日益重要的順序獨立對它們進行排序。所以，你按數字排序，然後按字符串排序。

struct Foo { 
    std::string name; 
    int count; 
    struct NameLess { 
    bool operator()(const Foo &lhs, const Foo &rhs) const { 
     return lhs.name.compare(rhs.name) < 0; 
    } 
    }; 
    struct CountLess { 
    bool operator()(const Foo &lhs, const Foo &rhs) const { 
     return lhs.count < rhs.count; 
    } 
    }; 
}; 

std::vector<Foo> foos; 
// ... 
std::stable_sort(foos.begin(), foos.end(), Foo::CountLess()); 
std::stable_sort(foos.begin(), foos.end(), Foo::NameLess());

你寧願先明顯，但後者可以派上用場保持組合和/或運行時配置的算法簡單。

參考：

cplusplus.com C++ : Reference : STL Algorithms : stable_sort

cplusplus.com C++ : Reference : STL Algorithms : sort

來源

2011-11-30 21:47:20

如果你要使用多種排序，你會按照日益重要的順序排序嗎？喜歡：sort（nums）;排序（字符串）; ...;排序（moreImportantCriteria）; ？ – HJM

'std :: sort'不穩定，所以如果您使用多種排序方式，那麼*無法保證*如果以前的排序對最終結果有任何影響。 –

@霍維是的，那是我試圖溝通。這與使用單個比較器版本不同。 –