c++ - 对bubblesort方法感到好奇

我在这里创建了一个简单的bubbleorting脚本，该脚本接受数组并对它们进行排序，这只是代码的一部分。但是它是对它进行排序的代码。我要这样做，而不是例如在每次通过时都不进行九个左右的比较，而是修改气泡排序，以在第二次通过时减少八个或一个以下比较，在第三次通过时减少七个，依此类推。我完全不知道该如何执行。最好的主意是什么？

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

最佳答案

您的代码已经在执行您想要的操作。由于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

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

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

关于c++ - 对bubblesort方法感到好奇，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7909788/