快速排序-比较/交换计数器

Question

早上好。我编写了一个程序，在一个包含2000项的数组上实现了几种不同的排序方法，并为每种排序方法生成了比较和交换的数量。

当我选择快速排序方法时，它会给出以下输出：

“交易所数目:1

比较数:2

交易所数目:1

比较数:2

交易所数目:1

比较数:6

交易所数目:1

比较数:2

交易所数目:1

..。

..。

快速分拣完成。

这是一个使用气泡的例子，我希望输出是这样的：

比较数目:1999年

交易所数目:0

气泡分类完成。

我知道我需要移动比较和交换计数器，但我不知道要将它们移到哪里才能收到预期的结果。

有人能帮忙吗？

我真的很感激！快把我逼疯了。

以下是我的快速排序代码：

    // QUICK SORT
public static void quickSort(AnyType[] array, int low, int high)
{
    int i = low, j = high, comparisons = 0, exchanges = 0;
    AnyType temp, pivot = array[(low + high)/2];

    while (i <= j)
    {
        while(array[i].isLessThan(pivot))
        {
            i++;
            comparisons++;
        }
        while(array[j].isBetterThan(pivot))
        {
            j--;
            comparisons++;
        }
        if (i <= j) {
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i++;
            j--;
            exchanges++;
        }
    }

    if (low < j) 
    {
        quickSort(array, low, j);
    }
    if (i < high) 
    {
        quickSort(array, i, high);
    }

    System.out.println("Number of comparisons: "+ comparisons);
    System.out.println("Number of exchanges: "+ exchanges);
}

Answer 1

您正在递归地调用quickSort()本身。对于每次迭代，当它从后续调用返回时，它将执行println代码。您需要确保打印代码仅在方法的最外层(第一次)迭代时执行。