两个气泡排序回路的实际区别
我的老师告诉我，这是泡泡类的唯一代码：
int a[] = {2, 3, 7, 9, 8, 1, 4, 5, 10, 6};
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a.length - i - 1; j++) {
if (a[j] > a[j + 1]) {
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
}
}
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + "\t");
}但我运行的程序有一个不同的外部循环：
int b[] = {2, 3, 7, 9, 8, 1, 4, 5, 10, 6};
for (int i = 0; i < b.length - 1; i++) {
for (int j = 0; j < b.length - i - 1; j++) {
if (b[j] > b[j + 1]) {
int t = b[j];
b[j] = b[j + 1];
b[j + 1] = t;
}
}
}
for (int i = 0; i < b.length; i++) {
System.out.print(b[i] + "\t");
}产出如下：
第一宗案件：
1 2 3 4 5 6 7 8 9 10第二宗案件：
1 2 3 4 5 6 7 8 9 10因此，现在有人告诉我，我的代码是错误的，即使我的输出是正确的。
拜托，告诉我我完全错了吗？
回答 3
Stack Overflow用户
发布于 2014-01-22 15:51:18
这两个版本都将正确排序。然而，第一个版本总是会执行额外的(不必要的)传递，因为它的执行N通过，而如果考虑到它，元素可能改变位置的最大次数是N1(当最小/最大的数字位于数组的错误端时)。
因此第二个版本更有效，它将复杂度从大约O(N*N)降低到O(N*(N1))。基本上是一样的。
所以，你的老师应该认识到你的代码是正确的。由于老师经常被困在他们的思维模式中，所以当你与他交谈时，要对此保持外交态度，并小心地引导他得出以上结论，即N-1外传就足够了。
Stack Overflow用户
发布于 2014-01-22 15:23:26
这是一个已知的泡沫排序优化的开始：sort
Stack Overflow用户
发布于 2014-01-22 15:11:13
外部循环不会对所有元素进行迭代。查看b.ength-1 for(int i=0;i<b.length-1;i++)。这意味着，如果您有10个元素，您将迭代到第8个元素。因为您同时使用<和length-1。如果你想坚持使用.length-1。您应该将条件更改为i<=b.length-1。
https://stackoverflow.com/questions/21285770
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号