java - 如何计算插入排序中的比较和交换次数？ (JAVA)

Question

public class Sorting
{
   public static int numOfComps = 0,
                     numOfSwaps = 0;

   public static void insertionSort(int[] array)
   {
      int unsortedValue;  // The first unsorted value
      int scan;           // Used to scan the array

      // The outer loop steps the index variable through 
      // each subscript in the array, starting at 1. The portion of
      // the array containing element 0  by itself is already sorted.
      for (int index = 1; index < array.length; index++)
      {
         // The first element outside the sorted portion is
         // array[index]. Store the value of this element
         // in unsortedValue.
         unsortedValue = array[index];

         // Start scan at the subscript of the first element
         // outside the sorted part.
         scan = index;

         // Move the first element in the still unsorted part
         // into its proper position within the sorted part.
         while (scan > 0 && array[scan-1] > unsortedValue)
         {
            array[scan] = array[scan - 1];
            scan--;

                // Counts the number of values swaps
                numOfSwaps ++;
         }

         // Insert the unsorted value in its proper position
         // within the sorted subset.
         array[scan] = unsortedValue;

         // Counts the number of values comparisons
        numOfComps ++;
      }
        System.out.println("\n\nNumber of comps = " + numOfComps);
       System.out.println("Number of swaps = " + numOfSwaps);       
   }
}

新人又来了。如何用 Java 编写这个插入排序程序来计算比较次数和交换次数？我已将比较和交换代码插入到程序中，但不确定它们是否位于正确的位置。我已经发布了程序。谢谢你的帮助。

Answer 1

比较次数是执行array[scan-1] > unsortedValue的次数。这不是你计算的。

提示:

• while (EXPRESSION) { STATMENTS } 可以重写为 while (true) { if (!(EXPRESSION)) { break; } 声明 }

• !(EXPRESSION1 && EXPRESSION2) 可以重写为 !(EXPRESSION1) || !(表达式2).

• if (表达式1 || 表达式2) { 中断; } 可以重写为 if (EXPRESSION1) { break; } if (表达式2) { 中断; }。

<小时/>

该算法不会交换变量对的值。然而，存在一种形式的多变量交换(A⇒B，B⇒C，C⇒D，D⇒A)。这种情况发生的次数就是当 scan 与 index 不同时执行 array[scan] = unsortedValue 的次数。这不是你计算的。

<小时/>

注释:

• 您的代码有错误。当到达 array[scan] = unsortedValue; 时，scan 可以为 -1。当排序 2, 1 时会发生这种情况。

• 请注意，这是插入排序的一个糟糕的实现。应使用二分搜索而不是线性搜索。这会将最大比较次数从 N * N 减少到 N * log N。