c++ - 使用幻灯片而不是交换进行冒泡排序

Question

目前我被要求设计四种排序算法(插入、外壳、选择和冒泡)，我有 4 个中的 3 个工作得很好；唯一不能正常运行的是冒泡排序。现在，我很清楚普通冒泡排序如何使用临时变量交换两个索引，但棘手的部分是它需要使用数组 index[0] 作为临时变量而不是普通变量temp，用于交换，并将较低的数组变量向下滑动到列表的前面，并在传递结束时将最后一个索引分配给 temp，这是最大值。

我已经研究了一段时间，甚至试图查找引用文献，但遗憾的是我找不到任何东西。我希望其他人之前已经这样做过，并且可以提供一些有用的提示。这是最后的手段，因为我一直在用笔和纸修改和遍历通行证，试图找出我的 fatal error 。无论如何，我的代码如下...

void BubbleSort(int TheArray[], int size)
{
    for (int i = 1; i < size + 1; i++)
    {
        TheArray[0] = TheArray[i];
        for (int j = i + 1; j < size; j++)
        {
            if (TheArray[j] > TheArray[0])
                TheArray[0] = TheArray[j];
            else
            {
                TheArray[j - 1] = TheArray[j];
            }
        }
        TheArray[size- 1] = TheArray[0];
    }
}

感谢任何反馈；非常感谢。

Answer 1

如果我理解问题陈述，我认为您正在寻找类似的东西:

void BubbleSort(int theArray[], int size)
{
    for (int i = 1; i < size + 1; i++)
    {
        theArray[0] = theArray[1];
        for (int j = 1; j <= size + 1 - i; j++)
        {
            if (theArray[j] > theArray[0])
            {
                theArray[j-1] = theArray[0];
                theArray[0] = theArray[j];
            }
            else
            {
                theArray[j - 1] = theArray[j];
            }
        }
        theArray[size-i+1] = theArray[0];
    }
}

我认为您的代码遗漏的部分是，一旦找到新的最大值，您必须将其放回数组中，然后再将新的最大值放入 Array[0] 存储位置(请参阅 theArray[ j-1] = theArray[0] 比较后)。此外，内部循环希望每次少运行一个，因为最后一个元素将是当前的最大值，因此您不想重新访问这些数组元素。 (参见(int j = 1 ; j <= size + 1 - i ; j++))

为了完整起见，这是我用来(轻轻地)测试它的主要驱动程序:

int main()
{
    int theArray[] = { 0, 5, 7, 3, 2, 8, 4, 6 };
    int size = 7;

    BubbleSort(theArray, size);
    for (int i = 1; i < size + 1; i++)
        cout << theArray[i] << endl;
    return 0;
}