sorting - 在java中存储递归方法的增量

Question

我目前正在做的一个项目遇到了困难。我需要通过在递归方法中放置计数器进行比较和赋值来找到快速排序方法的效率。我如何对这些计数器求和？一旦方法结束并被调用，计数器就会设置回 0。我可以做什么来改进我的代码？我尝试将每个都存储在链接列表中，但这不起作用。

我的代码:

public class QuickSort {

    public static void quickSort(int[] array3){   
        System.out.println("\n" + "The efficiency of the quick sort is:");
        int comp = 0;
        int swap = 0;
        quickSort(array3, 0, array3.length - 1);
        System.out.println("\n");
        for (int index = 0; index < array3.length; index++){
            System.out.print(array3[index] + " | ");
        }
        System.out.println("\n" + "A(n)= " + swap);
        System.out.println("C(n)= " + comp);
        System.out.println("T(n)= " + (swap + comp));
    }

    public static void quickSort(int[] array3, int first, int last){
        if(last > first){
            int pivotIndex = partition(array3, first, last);
            quickSort(array3, first, pivotIndex - 1);
            quickSort(array3, pivotIndex + 1, last); 
        }
    }

    public static int partition(int[] array3, int first, int last){

        int pivot = array3[first];
        int low = first + 1;
        int high = last;
        int comp = 0;
        int swap = 0;
        while (high > low){
            while (low <= high && array3[low] <= pivot){
                low++;
                comp++;
            }
            while (low <= high && array3[high] > pivot){
                high--;
                comp++;
            }
            if (high > low){
                int temp = array3[high];
                array3[high] = array3[low];
                array3[low] = temp;
                swap = swap + 3;
                comp++;
            }
        }
        while (high > first && array3[high] >= pivot){
            high--;
            comp++;
        }
        if (pivot > array3[high]){
            array3[first] = array3[high];
            array3[high] = pivot;
            swap = swap +2;
            comp++; 

            System.out.println("A(n) = " + swap);
            System.out.println("C(n) = " + comp);
            return high;
        }
        else {
            System.out.println("C(n) = " + comp);
            return first;
        }
    }   
}

Answer 1

您可以仅使用类中定义的属性来跟踪计数器。

只需移动 comp 并交换到类中的属性，不要在 QuickSort 中重新定义它们。

public class QuickSort {

    static int comp = 0;
    static int swap = 0;

    public static void quickSort(int[] array3){            
        System.out.println("\n" + "The efficiency of the quick sort is:");
        comp = 0;
        swap = 0;
        quickSort(array3, 0, array3.length - 1);
        System.out.println("\n");
        for (int index = 0; index < array3.length; index++){
            System.out.print(array3[index] + " | ");
        }
        System.out.println("\n" + "A(n)= " + swap);
        System.out.println("C(n)= " + comp);
        System.out.println("T(n)= " + (swap + comp));
    }
    ...
}