冒泡排序的外环N值

我刚刚学习排序（不是第一次）。在Bubble排序中，我们有以下代码。冒泡排序的外环N值

int bubble_sort(int *arr, size_t n) { 

size_t i,j; 
    for(i=0;i<n;i++) { 
    for(j=0;j<n-1;j++) { 
      if(arr[j] > arr[j+1]) { 
        int temp = arr[j]; 
        arr[j] = arr[j+1]; 
        arr[j+1] = temp; 
      } 
    } 
} 

return 0; 
}

如同您所有看到，内部环路具有第（n-1）倍（在循环中），这是可以理解的（A [1]，A [I-1]是两个涉及在一次迭代），但外环有我n，但它也适用于我n-1。但大多数在互联网上的实现都有n作为外部循环值。做最坏的情况下，外环n-1工作正常5 4 3 2 1.只是想知道，如果有任何一组输入不适用于n-1次外环。如果有请发布并解释。谢谢。

来源

2012-10-09 howtechstuffworks

请注意，经典气泡排序的内部循环有n-i次迭代，而不是n-1。 – amit

N-1也很好。正如你所描述的，最坏的情况需要N-1掉期（因为最后必须成为第一个，反之亦然）。如果将i变量的打印添加到if语句的内部，则会看到它在上次迭代中从未调用过。这意味着循环的最后一次迭代永远不会导致任何交换。

虽然Bubblesort的一个更有效的实现并不使用for循环作为外部循环。看看下面的代码。你能看到执行差异吗？

int bubble_sort(int *arr, size_t n) { 
    size_t i,j; 
    int flag = 1; 
    while (flag) { 
     flag = 0; 
     for(j=0;j<n-1;j++) { 
      if(arr[j] > arr[j+1]) { 
       int temp = arr[j]; 
       arr[j] = arr[j+1]; 
       arr[j+1] = temp; 
       flag = 1; 
      } 
     } 
    } 
    return 0; 
}

通过设置只有当实际发生交换的标志，你最终会跳出循环更快，当你在一个平均情况是。

来源

2012-10-09 17:43:47 Joost

是的，我已经完成了这....这就是为什么我想找到真正的泡沫排序和有效的比较 – howtechstuffworks

当从复杂性的角度来看比较时，你会看到最坏的情况是相同的（加或减一些常数），而最好的情况是更好的（n而不是n^2），平均情况更好的是一个常数因子。 – Joost

最坏情况需要n-1次迭代的事实本身不足以使索赔正确。然而，声明是正确的，并且可以正式证明它（我试图在我的答案中提供如何证明的准则）。 – amit

不，没有这样的输入。

理性是在泡沫排序的证明。回想一下，当证明泡沫排序的i'th（外部）迭代 - i最后一个元素就位并排序。

因此，n-1迭代之后，最后n-1元件到位和排序，只留下剩余的第一元件 - 可以只在其正确的位置，所述阵列中的第一位置。

（因此，使用这种方法，我们可以证明是冒泡排序至多需要n-1外迭代）

还要注意：典型的泡沫排序只需要n-i在内部循环迭代（因为我上面提到的理性），而不是n-1。

来源

2012-10-09 17:49:22 amit

需要注意的是，必须从0到n-i而不是从i到n-1（这两个都是n-i迭代）。 – Joost

冒泡排序的外环N值

回答

相关问题