两个冒泡排序循环之间的实际区别

Question

我的老师告诉我,这是Bubble Sort的唯一代码

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

所以现在我被告知我的代码是错误的,即使我的输出是正确的.拜托,告诉我,我完全错了？

Answer 1

两个版本都会正确排序。然而，第一个版本总是会做一个额外的（不必要的）传递，因为它做了 N 次传递，而如果考虑一下，一个元素可能改变位置的最大次数是 N-1（这将是最小/最大数位于数组的错误末尾）。

所以第二个版本更有效一点，它将复杂度从大约 O(N*N) 降低到 O(N*(N-1))。这在很大程度上是相同的。

所以，你的老师应该认识到你的代码是正确的。由于老师经常被困在他们的思维模式中，所以当你和他交谈时要外交一点，并小心地引导他得出上面的结论，N-1个外传就足够了。