如何根据长度对数组的字符串进行排序THEN字母顺序？

Question

我这样做是因为一个网站，我学习编程，我根本无法将我的头围绕此。

#include <iostream> 
#include <algorithm> 
#include <string> 
#include <vector> 
using namespace std; 

int main() 
{ 
    int n; 
    string thename; 
    vector <pair<string,int>> name; 
    cin >> n; 
    for (int i = 0; i < n; i++) 
    { 
     cin >> thename; 
     name.push_back(make_pair(thename, thename.length())); 
    } 
    sort(name.begin(), name.end()); 
    sort(name.begin(), name.end(), 
    [](const pair<string, int>& lhs, const pair<string, int>& rhs) { 
      return lhs.second < rhs.second; }); 
    for (int i = 0; i < n; i++) 
    { 
     cout << name[i].first<< endl; 
    } 
} 

我的高级建议我不使用lambda排序，因为我自己还是不太了解它。但我仍然会接受任何lambda排序的答案。 任何人都可以帮助我吗？

Answer 1

问题是std::sort不稳定 - 这意味着当您按长度排序时，按名称排序排序。

该容易方式做到这一点，是扭转你的一对。 std::pair有一个operator <，它比较first的值，如果它们相同，则比较second的值。所以，你需要的是：

#include <iostream> 
#include <algorithm> 
#include <string> 
#include <vector> 
using namespace std; 
int main() 
{ 
    int n; 
    vector <pair<int,string>> name; 
    cin >> n; 
    for (int i = 0; i < n; i++) 
    { 
     string thename; 
     cin >> thename; 
     name.push_back(make_pair(thename.length(),thename)); 
    } 
    sort(name.begin(), name.end()); 
    for (const auto& n: name) 
    { 
     cout << n.second << endl; 
    } 
} 

注意我提出thename环内（这是从来没有使用外），并取得了最后的循环foreach循环（这应该是你喜欢的环形状如果可能）。

但是你不需要在向量中存储长度。您只需存储名称，然后使用自定义比较器进行比较。

#include <iostream> 
#include <algorithm> 
#include <string> 
#include <vector> 
using namespace std; 
int main() 
{ 
    int n; 
    vector<string> name; 
    cin >> n; 
    for (int i = 0; i < n; i++) 
    { 
     string thename; 
     cin >> thename; 
     name.push_back(thename); 
    } 
    sort(name.begin(), name.end(), 
     [](const string& lhs, const string& rhs) 
     { 
      return std::tie(lhs.length(),lhs) < std::tie(rhs.length(), rhs); 
     }); 
    for (const auto& n : name) 
    { 
     cout << n << endl; 
    } 
} 

请注意，我用std::tie来比较长度和字符串。与std::make_pair相比，它的优点是它将默认使用引用，因此不会复制字符串。比自己做这件事的好处是，它是巨大更容易得到正确（并且它也更容易阅读）。

请注意，您可以通过手工编写一个仿函数替换拉姆达

[](const string& lhs, const string& rhs) 
{ 
    return std::tie(lhs.length(),lhs) < std::tie(rhs.length(), rhs); 
} 

：

struct MyLessString 
{ 
    bool operator() (const string& lhs, const string& rhs) const 
    { 
     return std::tie(lhs.length(),lhs) < std::tie(rhs.length(), rhs); 
    } 
}; 

，并使用它：

sort(name.begin(), name.end(), MyLessString{}); 

Answer 2

你并不需要一个vector<pair<int,string>存储你的字符串数组，你可以在vector<string>并写一个适当的排序函数，这里是一个N实施例：

#include <iostream> 
#include <algorithm> 
#include <string> 
#include <vector> 

int main() 
{ 
    int n; 
    std::string thename; 
    std::vector <std::string> name; 
    std::cin >> n; 
    for (int i = 0; i < n; i++) 
    { 
     std::cin >> thename; 
     name.push_back(thename); 
    } 
    sort(name.begin(), name.end(), 
    [](const std::string& lhs, const std::string& rhs) { 
      return lhs.size() == rhs.size() ? 
        lhs < rhs : lhs.size() < rhs.size(); }); 
    for (int i = 0; i < n; i++) 
    { 
     std::cout << name[i]<< std::endl; 
    } 
} 

输入：

4 
Joe 
Ann 
Ralph 
Andrew 

输出：

Ann 
Joe 
Ralph 
Andrew 

Answer 3

我提出pidgeonhole排序，随后经过某种每个pidgenhole的。

最初的步骤只有O（N + n），然后在O（p log p）中排序每个pidgeonhole，因为每个p总分类时间应该小于或等于O（n log n）

警告未经测试的代码：

#include <iostream> 
#include <algorithm> 
#include <string> 
#include <vector> 
using namespace std; 

constexpr const int MaxNameLength = 32; // arbitrary chosen length 

int main() { 
    int n; 
    string thename; 
    vector <vector<string>> name; 
    int maxLen = MaxNameLength; 
    name.resize(MaxNameLength); 
    cin >> n; 

    for (int i = 0; i < n; i++) { 
     cin >> thename; 
     if (name.length() > maxLen) { 
      name.resize(thename.length()); 
      maxLen = thename.length(); 
     } 
     name[thename.length()].emplace_back(thename); 
    } 

    for (auto& len: name) { 
     sort(len.begin(), len.end()); 
    } 

    for (int i = 0; i < n; i++) { 
     cout << name[i].first<< endl; 
    } 
}