Shaker/Cocktail 排序中的交换和比较次数 -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 次迭代。！

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

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

Shaker/Cocktail 排序中的交换和比较次数 -Java

Number of swaps and comparisons in Shaker/Cocktail sort -Java

java

sorting

comparison

swap

bubble-sort