1

我只是在学习排序（不是第一次）。在冒泡排序中，我们有以下代码。

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时间（在for循环中），这是可以理解的（a[i],a[i-1]都涉及一次迭代），但外循环有i < n，但它也适用于i < n-1. 但是互联网中的大多数实现都具有 n外循环值。对于最坏的情况，执行外循环n-1效果很好5 4 3 2 1。n-1只是想知道，是否有任何一组输入在外循环期间不起作用。如果有请发帖并说明。谢谢。

4

2 回答 2

3

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

不过，更高效的冒泡排序实现不使用 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-09T17:43:47.700 回答
1

不，没有这样的输入。

理性在冒泡排序的证明中。i回想一下，在冒泡排序的第 ' 次（外部）迭代中证明这一点时-i最后一个元素就位并排序。

因此，在n-1迭代之后，最后一个n-1元素就位并排序，只留下剩余的第一个元素——它只能在其正确的位置，即数组中的第一个位置。

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

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

于 2012-10-09T17:49:22.923 回答