c++ - 对冒泡排序方法感到好奇

Question

我在这里创建了一个简单的冒泡排序脚本，它接受数组并对它们进行排序，这只是代码片段。但它是对其进行排序的代码。我想这样做而不是在每次通过时进行九次左右的比较，而是修改冒泡排序以在第二次通过时进行八次或一次比较，第三次进行七次比较，依此类推。我完全不知道如何实现它。最好的主意是什么？

        int bubbleSortArray(int array[])
        {
            for(int i=0;i<10;i++)
            {
                for(int j=0;j<i;j++)
                {
                    if(array[i]>array[j])
                    {
                        swap(array[i], array[j]);
                        amountOfSwaps += 1;
                    }
                }
            }

        printArray(array);
        return amountOfSwaps;

        }


       void swap(int & value1, int & value2)
       {
              int temp=value1; 
              value1=value2;
              value2=temp;
       }

Answer 1

您的代码已经在做您正在寻找的事情。由于 j 迭代到长度 i，它每次都增加一个。我认为您感到困惑，因为您的代码实际上是从问题中的英语向后实现的；)

这是一个示例数组，以及每次迭代时将进行的修改。括号表示在每次迭代中检查数组的哪一部分:

(7)5 3 8 6 9 4 2 0 1
(7 5)3 8 6 9 4 2 0 1
(7 5 3)8 6 9 4 2 0 1
(8 7 5 3)6 9 4 2 0 1
(8 7 6 5 3)9 4 2 0 1
(9 8 7 6 5 3)4 2 0 1
(9 8 7 6 5 4 3)2 0 1
(9 8 7 6 5 4 3 2)0 1
(9 8 7 6 5 4 3 2 0)1
(9 8 7 6 5 4 3 2 1 0)

正如您第一次看到的那样，实际上什么也没做，也永远不会，因为您正在将一个元素与自身进行比较。第二次通过你现在比较两个元素，然后是三个，然后依此类推。

为了使您的代码从比较所有代码开始，然后每次都少做一个(如您的问题所述)，您需要将循环修改为以下内容(注意 j<10-i):

    for(int i=0;i<10;i++)
    {
        for(int j=0;j<10-i;j++)
        {

无论哪种方式，它都等同于同一件事，并且最终会起作用。您可以通过设置 i = 1 进一步跳过与自身的第一次比较:

for(int i=1;i<10;i++)
    {
        for(int j=0;j<10-i;j++)
        {

这将省略上面的第一个比较，这是您正在寻找的另一个优化。