java - Shaker/Cocktail sort 中的交换和比较次数 -Java

Question

我研究了如何计算冒泡排序的交换和比较，并将振动排序程序修改为:

 public void shakerSort(int a[])  // http://www.geeksforgeeks.org/cocktail-sort/
{
    boolean swapped = true;
    comparisons = 0;
    swaps = 0;
    int start = 0;
    int end = a.length;

    while (swapped==true)
    {         
        swapped = false;

        for (int i = start; i < end-1; ++i)
        {
          comparisons++; //count comparisons
          if (a[i] > a[i + 1])
          {
             int temp = a[i];
             a[i] = a[i+1];
             a[i+1] = temp;
             swapped = true;

             swaps++; //count swaps
          }
        }

        if (swapped==false)
        {
            break; 
        }

        swapped = false;

        end = end-1;

        for (int i = end-1; i >=start; i--)
        {
          comparisons++; //count comparisons
            if (a[i] > a[i+1])
            {
                int temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                swapped = true;
                swaps++; //count swaps
            }
        }

        start = start+1;

    }

}

但是，对于包含 100 个元素的数组，其中比较次数应始终为 4950 ( n(n-1)/2 )，它给出的值每次运行程序时都会发生变化 - 并且该值始终为小于 4950。

为什么会这样，我该如何解决它？

(注意:每次程序运行时数组都是随机的)

另外，交换数量还可以吗？

Answer 1

让我们举个例子来了解计数的变化:

array[5] = { 2 , 1 , 3 , 4 , 5 }

需要多少次迭代？

首先，摇床排序会在每次迭代中从头开始检查，然后从最后开始检查。 count 开始时为 0。

 2 , 1 , 3 , 4 , 5 --> count = 1
 ^   ^
 it will swap 2 and 1
 swap count++

 1 , 2 , 3 , 4 , 5  --> count = 2
             ^   ^
 no swap

程序将再次检查，因为swap = true

 1 , 2 , 3 , 4 , 5 --> count = 3
     ^   ^
  no swap

 1 , 2 , 3 , 4 , 5  --> count = 4
         ^   ^
 no swap

程序将结束，因为现在 swap = false。

<小时/>

现在让我们采用不同的数组:

array[5] = { 5 , 4 , 3 , 2 , 1 }

同样，迭代次数将远多于 4 次迭代。!

<小时/>

因此，对于相同大小的数组和不同的值，迭代次数会不同。!

注意:交换计数和迭代计数在程序中完美使用:)