气泡排序算法中的外环

我一直在谷歌上搜索，并且找不到类似的问题或解释。气泡排序算法中的外环

假定以下代码：

int out, in; 
for(out=nElems-1; out>1; out--) 
    for(in=0; in<out; in++) { 
     if(a[in] > a[in+1]) 
      swap(in, in+1); 
    }

当外值达到1后为什么外循环停止？它不应该有2个元素吗？ 0和1的地方？是什么让我们确信他们已经被分类？

我明白这个算法是如何工作的，并且意识到如果没有完成迭代就会停止一个标志，这会有更好的解决方案，但是我对理解上面的代码非常感兴趣。

来源

2014-09-13 Lifter

不应交换是'交换（一个[IN] ，a [in + 1]）'？你拥有它的方式是交换索引，而不是实际排列数据 – nem035 2014-09-13 18:04:11

你试过对上面的代码做空运行吗？ – zerocool 2014-09-13 18:05:35

从书中复制而来。虚拟交换会照顾到这一点。 :) – Lifter 2014-09-13 18:05:43

当输出达到2时，内循环从0变为1.它确保[0]和[1]两个元素的顺序正确 - 这是停止冒泡排序的时间。然而，上面提供的代码会比较[1]和[2] - 导致潜在的交换导致未排序的数组（因为[1]和[2]之后[0]和[1]应该再次进行比较相比）。为了使这个代码正常工作，外层循环应该包含在内，所以for (out = nElems - 1; out > 0; out--)。

你需要在这里看到的事实是，在气泡排序内部循环正在做排序的实际工作（通过交换元素）。外层循环只是设置超出所有元素已经排序的限制。

来源

2014-09-13 18:06:35 3yakuya

你错了，它确保[0]和[1]的顺序正确，但是[2]可能会取代[1]和它没有被检查[0] – Kyborek 2014-09-13 18:32:35

啊，我明白了。该书的代码似乎是错误的。一个[in + 1]是我没有看到的东西。谢谢。 – 3yakuya 2014-09-13 19:27:48

所以，恐怕这本书代码不起作用，让我们通过实例证明：

Array ={3,2,1};//nvm the syntax, i assume pseudocode because we don't even know what is swap() 
nElems=3; 
For: out=2; 
For:in=0 
    check 0 and 1 
    Array={2,3,1} 
in=1 
    check 1 and 2 
    Array={2,1,3} 
in=2, break; 
out=1, break;

你可以看到流量与数组{2,1,3}这是没有排序结束。因此，即使书本可能有错误，或者如果你阅读了几页，你可能会发现它是故意的。正确冒泡排序将具有条件out>=1或out>0

编辑：用阵列由2种元素的，算法将什么都不做，甚至simplier证明

Array ={2,1}; 
nElems=2; 
For: out=1, break;//out = nElems-1, 1>1 is false

来源

2014-09-13 18:06:47 Kyborek

这个循环是否会说'out = 1'，这个时候不会中断，因为终止条件是out> 1'。我错了吗，还是不清楚东西？我可能是错的，但我猜更多的是困惑。 – 2014-09-13 18:18:50

你说得对，让我重新思考 – Kyborek 2014-09-13 18:24:30

气泡排序算法中的外环

回答

相关问题