2

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

        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;
       }
4

3 回答 3

1

我认为你的循环j有点倒退。我认为你需要类似的东西：

for (int i = 0; i < 10; i++) {
    for (int j = 1; j < 10 - i; j++) {
        // ...
    }
}
于 2011-10-26T22:50:39.133 回答
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++)
        {

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

于 2011-10-26T23:19:36.260 回答
0

请注意，冒泡排序的一个显着特性是它检查是否在每次通过时都执行了交换。如果它没有交换，那么一切都井井有条，你可以早点休息。像这样的东西：

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;
}
于 2011-10-26T23:05:25.757 回答