打印变量未按预期工作 - Java

Question

我想统计快速排序算法中比较和交换的次数。这是我的代码：

public ArrayList<Integer> quickSort(ArrayList<Integer> data , int low , int high , int comparisons ,int swaps ){

    ArrayList<Integer> sortedData = new ArrayList<Integer>();

    if(low< high) {
        int pivotIndex = low; // Assume first element is the pivot
        int pivot = data.get(low);// The pivot value
        data.set(pivotIndex, data.get(high));// Swap pivot with last item

        data.set(high, pivot);
        int i = low - 1;
        int j = high;


        do {                
            do {i++;} while (data.get(i)< pivot);
            do {j--;} while (j>=0 && data.get(j)> pivot);
            comparisons ++ ;
            if (i < j) {
                int temp = data.get(i);
                data.set(i, data.get(j));
                swaps ++ ;
                data.set(j, temp);
                swaps ++ ;
            }  
        } while (i < j);

        data.set(high, data.get(i));  // Put the pivot back in the middle
        swaps ++ ;
        data.set(i, pivot);
        swaps ++ ;

        quickSort(data, low, i - 1 , comparisons , swaps);// Recursive sort left list
        quickSort(data, i + 1 ,high ,comparisons , swaps);// Recursive sort right list
    }

    System.out.println("Quick S swaps :   " + swaps);
    System.out.println("Quick S comparisons :   " + comparisons);

    sortedData = data;

    return sortedData ; 
}

虽然我将打印语句放在循环和递归函数之后，但输出是每个循环的交换和比较！！它们也会增加直到特定点然后减少到 return 回到他们的起点 !!

Quick S swaps :   2
Quick S comparisons :   1
Quick S swaps :   4
Quick S comparisons :   2
Quick S swaps :   6
Quick S comparisons :   3
Quick S swaps :   8
Quick S comparisons :   4
Quick S swaps :   10
Quick S comparisons :   5
..
..
..
..
..
Quick S swaps :   2986
Quick S comparisons :   1493
Quick S swaps :   2988
Quick S comparisons :   1494
Quick S swaps :   2990
Quick S comparisons :   1495
Quick S swaps :   2992
Quick S comparisons :   1496
Quick S swaps :   2994
Quick S comparisons :   1497
Quick S swaps :   2998
Quick S comparisons :   1499
Quick S swaps :   2998
Quick S comparisons :   1499
Quick S swaps :   2998
Quick S comparisons :   1499
Quick S swaps :   2994
Quick S comparisons :   1497
Quick S swaps :   2992
Quick S comparisons :   1496
Quick S swaps :   2990
Quick S comparisons :   1495
Quick S swaps :   2988
Quick S comparisons :   1494
Quick S swaps :   2986
Quick S comparisons :   1493
..
..
..
..
..
Quick S swaps :   12
Quick S comparisons :   6
Quick S swaps :   10
Quick S comparisons :   5
Quick S swaps :   8
Quick S comparisons :   4
Quick S swaps :   6
Quick S comparisons :   3
Quick S swaps :   4
Quick S comparisons :   2
Quick S swaps :   2
Quick S comparisons :   1

为什么会这样？？我该如何修复它？？

Answer 1

int comparisons 和 int swaps 以及放置在调用堆栈上的局部变量。每次调用 quickSort(ArrayList<Integer> data , int low , int high , int comparisons ,int swaps) 都有自己的这些变量副本。

每次进行递归调用时，都会将这些变量的较高值传递给下一次调用，但在递归调用时 returns，您会看到这些变量较早副本的较低值。

如果你想要单个 comparisons 变量和单个 swaps 变量，你可以将它们设为静态或包含 quickSort 方法的 class 的实例变量（并将它们从方法签名中删除）。

至于多次打印的变量，您必须将 println 语句移到递归方法之外，因为该方法被多次调用，并且每次打印这些变量。

例如：

...

private int comparisons = 0;
private int swaps = 0;

public ArrayList<Integer> quickSort(ArrayList<Integer> data , int low , int high)
{
    ...
}

public printCounters()
{
    System.out.println("Quick S swaps :   " + swaps);
    System.out.println("Quick S comparisons :   " + comparisons);
}

....

someObj.quickSort(data, 0, data.size() - 1); // sort the list
someObj.printCounters(); // print the counters

作为替代方案，正如 JB Nizet 评论的那样，您可以传递一些可变计数器。

例如，一个int数组：

someObj.quickSort(data, 0, data.size() - 1, new int[]{0}, new int[]{0});

和

public ArrayList<Integer> quickSort(ArrayList<Integer> data , int low , int high , int[] comparisons ,int[] swaps)
{
    // here you change each comparisons++ to comparisons[0]++ 
    // and each swaps++ to swaps[0]++
    // you also print comparisons[0] and swaps[0]
}

打印变量未按预期工作 - Java

Printing variables doesn't work as expected - Java

java

quicksort