对冒泡排序方法感到好奇

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++)
        {

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

Answer 2

我认为您的 j 循环有点向后。我认为你需要类似的东西：

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

Answer 3

请注意，冒泡排序的一个显着特性是它检查每次传递是否都执行了交换。如果它没有交换，那么一切都井然有序，你可以提前休息。像这样的事情：

int bubbleSort(int *arry, size_t size)
{
  bool swapped;
  size_t upper_bound = size;
  int amountOfSwaps = 0;

  do
  {
    swapped = false;
    for(int i = 1; i < upper_bound; ++i)
    {
      if(arry[i] < arry[i - 1])
      {
        swap(arry[i], arry[i - 1]);
        swapped = true;
        ++amountOfSwaps;
      }
    }
    --upper_bound;
  }while(swapped);

  return amountOfSwaps;
}