快速排序打印比较

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;

}

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

 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;

无论你的主要排序函数在哪里，只要在调用它之后放置这些打印语句：

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

快速排序打印比较

quicksort printing comparison

java

quicksort