快速排序打印比较

Question

下面是快速排序分区方法中的代码：

public static void quickSort(int[] array) 
{
doQuickSort(array, 0, random1.length - 1);

 }
 private static void doQuickSort(int[] array, int start, int end)
 {
int pivotPoint;

 if(start < end)
 {
   pivotPoint = partition(array, start, end);

    doQuickSort(array,start, pivotPoint - 1);

    doQuickSort(array, pivotPoint +1, end); 
    }


  }
 private static int partition(int[] array, int start, int end)
{
int pivotValue = array[start];
int endOfLeftList = start;
int mid = (start + end)/2;;
int compare = 0;
int swap = 0;

  for(int scan = start + 1; scan <= end; scan++)
  {
   compare++;
   if(array[scan] < pivotValue)
   { 
     swap++;
     endOfLeftList++;
      swap(array, endOfLeftList, scan);
   }
  }

    System.out.println("\nComparisons: " + compare); 
    System.out.println("Swaps: " + swap);

  swap(array, start, endOfLeftList);

  return endOfLeftList;

}

使用随机生成的数组，似乎不管我把print语句放在哪里，当我调用整个快速排序方法时，它都会像这样连续地打印：

 Array Before QuickSort:
 40 27 13 58 42 41 84 4 75 96 
 Comparisons: 1
 Swaps: 1

 Comparisons: 2
 Swaps: 2

 Comparisons: 3
 Swaps: 2

 Comparisons: 4
 Swaps: 2

 Comparisons: 5
 Swaps: 2

 Comparisons: 6
 Swaps: 2

 Comparisons: 7
 Swaps: 3

 Comparisons: 8
 Swaps: 3

 Comparisons: 9
 Swaps: 3

 Comparisons: 1
 Swaps: 0

 Comparisons: 2
 Swaps: 0

 Comparisons: 1
 Swaps: 1

 Comparisons: 1
 Swaps: 1

 Comparisons: 2
 Swaps: 1

 Comparisons: 3
 Swaps: 1

 Comparisons: 4
 Swaps: 1

 Comparisons: 5
 Swaps: 1

 Comparisons: 1
 Swaps: 1

 Comparisons: 2
 Swaps: 2

 Comparisons: 3
 Swaps: 2

 Comparisons: 1
 Swaps: 1

 Array After QuickSort:
 4 13 27 40 41 42 58 75 84 96 

我一定是忽略了什么，但我只是不确定。我试图让它只打印一次，说明多少次比较，多少次掉期。如果需要，我会用更多的信息进行编辑。

Answer 1

之所以会发生这种情况，是因为为了快速排序，您可能会调用partition方法很长时间，直到数组被排序。因此，要只获得一次总计数，并且在流程完成之后，您应该这样做：

使这些变量成为全局变量：

int compare = 0;
int swap = 0;

在您的主要排序函数所在的地方，只需将这些print语句放在调用它之后：

System.out.println("\nComparisons: " + compare); 
System.out.println("Swaps: " + swap);

编辑

因此，根据您编辑的问题，您应该在quickSort方法中包含如下打印语句：

public static void quickSort(int[] array) 
{
    doQuickSort(array, 0, random1.length - 1);
    System.out.println("\nComparisons: " + compare); 
    System.out.println("Swaps: " + swap);
}

或者在你像这样称呼quickSort之后：

quickSort(someIntArray);
System.out.println("\nComparisons: " + compare); 
System.out.println("Swaps: " + swap);

Answer 2

每次打印比较的原因是，每次需要分区时都要使用这个函数，对于快速排序来说，分区是多次的。

如果您只想显示结束，那么您应该创建一个单独的函数来打印比较的数量。

例：

void printComparisons(int compare, int swap){
     System.out.println("\nComparisons: " + compare); 
     System.out.println("Swaps: " + swap);
}