arrays - 冒泡排序的外循环N值

Question

我刚学排序(不是第一次)。在冒泡排序中，我们有以下代码。

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外循环次数。如果有请发帖并说明。谢谢。

Answer 1

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;
}

通过仅在实际交换发生时设置标志，在一般情况下，您最终会更快地跳出循环。