冒泡排序算法保持数组不变

Question

我正在尝试编写一个简单的冒泡排序算法，但它不起作用。最后打印时数组不变

我已经在我的 IDE 上使用了调试工具，它告诉我第二个 for 循环没有递增，但我不知道为什么不是。

总的来说，我对学习 C++ 和算法还是陌生的，所以对此的指点会很有帮助。

这是代码，非常感谢。

#include <iostream>

int main(){
    int A[] = {13, 89, 43, 74, 45, 16};
    int n = sizeof(A)/sizeof(*A);

    for (int i=0; i<n; i++) { //pass through the algorithm n-1 times
        int flag = 0;
        for (int j=0; j<n-i-1; j++) { //optimise checks, avoid checking sorted part of array
            if (A[j] > A[j+1]) {
                int temp = A[j];
                A[j] = A[j+1];
                A[j+1] = temp;
                flag = 1; //shows a swap happened
            }
            if (flag == 0) { //no swaps have occurred so the loop is over
                break;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        std::cout << A[i] << " ";
    }
    return 0;
}

Answer 1

你的算法有误。您应该在 flag 第二个循环完成后 检查

    int flag = 0;
    for (int j=0; j<n-i-1; j++) { //optimise checks, avoid checking sorted part of array
        if (A[j] > A[j+1]) {
            int temp = A[j];
            A[j] = A[j+1];
            A[j+1] = temp;
            flag = 1; //shows a swap happened
        }
    }
    if (flag == 0) { //no swaps have occurred so the loop is over
        break;
    }

事实上，您在第二个循环之前初始化标志，但在第二个循环中检查它应该是一个线索，表明某些地方不太正确。所以应该让调试器告诉你第二个循环没有递增。

有时，当您查看自己的代码时，您只会看到您认为自己编写的内容，而不是您实际编写的内容。客观地看自己的代码是需要培养自己的习惯。

Answer 2

只有一个错误：

    if (flag == 0) { //no swaps have occurred so the loop is over
        break;
    }

这应该在第二个 for 循环之外。

#include <iostream>

int main(){
    int A[] = {13, 89, 43, 74, 45, 16};
    int n = sizeof(A)/sizeof(*A);

    for (int i=0; i<n; i++) { //pass through the algorithm n-1 times
        int flag = 0;
        for (int j=0; j<n-i-1; j++) { //optimise checks, avoid checking sorted part of array
            if (A[j] > A[j+1]) {
                int temp = A[j];
                A[j] = A[j+1];
                A[j+1] = temp;
                flag = 1; //shows a swap happened
            }
        }
            if (flag == 0) { //no swaps have occurred so the loop is over
                break;  
        }
    }
    for (int i = 0; i < n; i++) {
        std::cout << A[i] << " ";
    }
    return 0;
}

Answer 3

最初当A[j] > A[j+1]被选中时，13 > 89 为假，flag 保持为 0 并执行 break 语句。这就是数组没有变化的原因。如其他答案中所述，您应该在第二个循环完成后检查标志。你听说过橡皮鸭调试吗？试试看。很有帮助。

冒泡排序算法保持数组不变

Bubble Sort algorithm leaves array unchanged

c++

algorithm

bubble-sort