c++ - 在没有附加库的情况下按字母顺序对给定文本进行排序

Question

我的作业是编写一个按字母顺序对给定文本进行排序的应用程序。为此，我只能使用“vector”、“string”和“iostream”库。

我成功了，但现在遇到了奇怪的问题 - 当我尝试对短文本进行排序时，一切正常，但输入较长的程序似乎陷入无限循环或效率问题。例如在文本中

"Albert Einstein 14 March 1879 – 18 April 1955 was a German-born theoretical physicist who developed the theory of relativity one of the two pillars of modern physics alongside quantum mechanics His work is also known[...]" 

一切正常，直到“力学”短语。添加这个或任何其他词后，程序将像我之前提到的那样永远运行。

恐怕我必须在这种情况下粘贴整个代码(请原谅)。

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

int compare(std::string first, std::string second){
    int flag = 1;
    int i;
    if (first.size() <= second.size()){
        for (i = 0; i<first.size(); ++i ){
            if (first[i] == second[i]){
                continue;}
            else if (first[i] > second[i]){
                flag = 0;
                break;}
            else {
                break;}}}
    else {
        for (i = 0; i<second.size(); ++i ){
            if (first[i] == second[i]) {
                continue;}
            else if (first[i] > second[i]){
                flag = 0;
                break;}
            else {
                break;}
        }
        int m = second.size() - 1;
        if (first[m] == second[m]){
                flag = 0;}}
return flag;}


int main() {
    std::vector<std::string> text;
    std::string word;
    std::string tmp;
    while(std::cin >> word){
        text.push_back(word);}
    int mistakes, m = 1;
    while(m) {
        mistakes = 0;
        for (int index = 1; index < text.size() ; ++index){
            if (!(compare(text[index-1], text[index]))){
                tmp = text[index];
                text[index] = text[index-1];
                text[index-1] = tmp;
                mistakes += 1;}}
        m = mistakes;}
    for (auto element: text){
        std::cout << element << " ";}}

我很想知道如何解决它以及为什么会出现这个问题 - 至少执行时间不会随着输入的长度而增长，但更像是“工作/不工作”，这与效率不同问题。

Answer 1

您错过了一些条件，因此您的 while 循环无限运行。例如:

1. 你的 错误 变量，如果第一对单词的顺序错误，你的 while 循环执行的值永远不会变为 0。负面测试用例是:“球苹果”。在这种情况下，您的代码会无限运行。

2. 在您的比较方法中，由于以下代码行测试用例(如“Apple ball”)给出了错误的答案。这里 first[m] = second[m] = l ，因此根据您的条件它将返回 false 并交换它们。它会将“Apple”替换为“Ball”，这是错误的。

   int m = second.size() - 1;
       if (first[m] == second[m]){
               flag = 0;
   }
   

3. 您还需要处理比较大写和小写单词的情况。例如:“月也”。在这种情况下，答案应该是“也是月”。因此，在比较两个字符串之前，您应该将它们置于相同的大小写，然后进行比较。

4. 1874应该在18之后的数字比较情况。(你可以加上这个)

Following is the corrected code.

---

#include <iostream>
#include <string>
#include <vector>
#include <cctype>

int compare(std::string first, std::string second){

    // this is to handle the comparison of two words with mixed case(upper/lower) of letters.
    // earlier solution failed for comparison between 'Month' and 'a'
    for(int i=0;i<first.size();i++){
        first[i] = tolower(first[i]);
    }

    for(int i=0;i<second.size();i++){
        second[i] = tolower(second[i]);
    }

    int flag = 1;
    int i;
    if (first.size() <= second.size()){
        for (i = 0; i<first.size(); ++i ){
            if (first[i] == second[i]){
                continue;}
            else if (first[i] > second[i]){
                flag = 0;
                break;}
            else {
                break;}}}
    else {
        for (i = 0; i<second.size(); ++i ){
            if (first[i] == second[i]) {
                continue;}
            else if (first[i] > second[i]){
                flag = 0;
                break;}
            else {
                break;}
        }

    }
    return flag;}


    int main() {
    std::vector<std::string> text;
    std::string word;
    std::string tmp;
    while(std::cin >> word){
        text.push_back(word);}



    // bubble short
    for(int i=0;i<(text.size()-1);i++){

        for(int j=0;j<(text.size()-1-i);j++){
            if (!(compare(text[j], text[j+1]))){
                tmp = text[j];
                text[j] = text[j+1];
                text[j+1] = tmp;
            }
        }
    }



    for (auto element: text){
        std::cout << element << " ";}}