打印变量不像预期那样工作- 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 ; 
}

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

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)的调用都有自己的这些变量的副本。

每次进行递归调用时，都会将这些变量的更高值传递给下一次调用，但当递归调用返回时，会看到这些变量先前副本的较低值。

如果您想要一个comparisons变量和一个swaps变量，可以使它们成为包含quickSort方法的类的静态变量或实例变量(并从方法签名中删除它们)。

对于多次打印的变量，您必须将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所评论的，您可以传递一些可变计数器。

例如，一个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]
}