1

我只是想弄清楚一个项目使用冒泡排序交换了多少次。

当我在 Windows 上实现它时，它可以完美运行。但是用 g++ 在 Linux 上实现它，输出完全不同，我要疯了，试图找出错误。

这是我的气泡排序功能

int bubbleSort(string s){
int num = 0;

// Bubble sort string and count inversions on each swap
for (int i = 0; i < s.length(); i++) {
    for(int j = 0; j < s.length() - 1; j++) {
        if(s[j] > s[j+1]) {
            swap(s[j], s[j+1]);
            num++;
        }
    }
}
return num;
}

任何人都可以看到这段代码有什么问题，这可能会给我在 Windows 和 Linux 之间带来问题吗？

测试输入：GCAD

应该返回 6，但 G++ 返回 10

4

2 回答 2

3

我修改了您的代码以提供完整的工作程序：

#include <iostream>

int bubbleSort(std::string s) {
  int num = 0;
  for (int i = 0; i < s.length(); i++) {
    for(int j = 0; j < s.length() - 1; j++) {
      if(s[j] > s[j+1]) {
        std::swap(s[j], s[j+1]);
        num++;
        std::cout << "num is " << num << " and string is " << s << "\n";
      }
    }
  }
}

int main(void) {
  bubbleSort("ZWQM");
}

在 64 位 Linux 机器上编译它g++。跑了。结果：

num is 1 and string is WZQM
num is 2 and string is WQZM
num is 3 and string is WQMZ
num is 4 and string is QWMZ
num is 5 and string is QMWZ
num is 6 and string is MQWZ

六次迭代，对字符串进行排序。请确认这个确切的程序不会为您产生这个确切的输出......并告诉我们它做了什么。

编辑我找到了一种方法来得到答案10！我在字符串中添加了一个换行符。

bubbleSort("ZWQM\n");

结果是

num is 1 and string is WZQM

num is 2 and string is WQZM

num is 3 and string is WQMZ

num is 4 and string is WQM
Z
num is 5 and string is QWM
Z
num is 6 and string is QMW
Z
num is 7 and string is QM
WZ
num is 8 and string is MQ
WZ
num is 9 and string is M
QWZ
num is 10 and string is
MQWZ

请注意回车如何与输出混淆，因为它“冒泡”到第一个字符位置。我现在 99% 确信您观察到的差异与您将字符串放入程序的方式有关——Windows 和 Linux 对行尾的处理方式不同。

于 2013-10-10T05:37:32.370 回答
0

应修改循环终止条件以进行不必要的比较，如下所示：

for (int i = 0; i < s.length()-1; i++) {         
    for(int j = 0; j < s.length() - i - 1; j++) {
        if(s[j] > s[j+1]) {
            swap(s[j], s[j+1]);
            num++;
        }
    }
}

在每次迭代之后，总是对最后一个元素进行排序。

于 2013-10-10T05:14:01.490 回答