冒泡排序代码可能出了什么问题？

Question

我有一个问题，代码对“tab”进行了良好的排序，返回了正确的结果，但是“tab2”却返回了错误的结果（7 6 4 0 4 1 3 1 5 6 6 7 8 9 9）。 不幸的是，我在代码中没有发现任何错误，一切看起来都是正确的。

#include <iostream>

void sort(int* begin, int* end) {
    for (int* i = begin; i != end; ++i) {
        //std::cout << *i<< std::endl;

        for (int* j = i+1 ; j < end ; ++j) {
            //std::cout << *(j - 1)<<" " << *j << std::endl;
            if (*(j - 1) > *j) {
                std::swap(*(j - 1), *j);
            }
        }
    }
}

void write(int* begin, int size)
{
    while (size > 0)
    {
        std::cout << *begin << ' ';
        ++begin;
        --size;
    }
}

int main()
{
    int tab[10] = { 0, 9, 1, 3, 8, 2, 6, 7, 5, 4 };
    sort(tab, tab + 10);
    write(tab, 10);

    std::cout << '\n';

    int tab2[16] = { 9, 7, 8, 6, 5, 4, 4, 0, 9, 6, 7, 1, 6, 3, 1, -100 };
    sort(tab2, tab2 + 15);
    write(tab2, 15);
}

- karamba

---

建议：启动老式调试器并逐步执行“sort”函数，注意程序是否执行了您没有预期的操作，例如存储错误值或选择错误路径。这就是一个bug。 - user4581301

使用小而系统的测试案例，以便您可以在代码中跟随而不会迷失方向。我找到的最小失败案例是 { 3, 2, 1 }。（您会注意到一旦将 3 移到正确的位置，就会忽略数组的第一个元素，即 2。出于巧合，您的交换顺序与第一个数组一起工作。） - molbdnilo

顺便说一句，在C++中通常没有好的理由使用C风格数组，因为它们与语言中的任何其他类型行为不同。通过使用C++的零开销、表现良好的等效容器——std::array，您将节省自己很多泪水。 - Brian61354270

Answer 1

你有两个循环，但只使用内部循环的索引进行比较和交换。经典的冒泡排序使用两个索引。外部索引处的元素得到其后面的最大值。

因此，修复方法如下：

            if (*i > *j) {
                std::swap(*i, *j);
            }

或者问题可能是内部循环的起始位置在最低值到达底部之前向前移动。如果在每次迭代后打印列表，您可以清楚地看到它。在这种情况下，修复方法是不要从外部循环的光标开始内部循环，而是从第一个元素之后开始。

    for (int* i = begin; i <= end; ++i) {
        for (int* j = begin+1 ; j <= end ; ++j) {
            if (*(j - 1) > *j) {
                std::swap(*(j - 1), *j);

- caujka