如何计算比较次数Java HeapSort

Question

我正在通过使用Java中的MinHeap（BinaryHeap）实现HeapSort算法。最后，我希望通过排序完成比较的总数。我整天都在努力找出应该增加计数器的界限，但是我遇到了很多麻烦，现在已经迷失了。您能帮我吗？

public class MinHeap {

    int numberOfComparisons;

    private int[] array;
    private int currentSize;

    private static final int DEFAULT_CAPACITY = 100;

    public MinHeap(){
        currentSize = 0;
        array = new int[DEFAULT_CAPACITY + 1];
    }

    public MinHeap(int size){
        currentSize = 0;
        array = new int[size + 1];
    }


    public void insert(int x){

        if(currentSize + 1 == array.length){
            doubleArray();
        }

        // percolate up
        int hole = ++currentSize;
        array[0] = x;

        while(x < array[hole/2]){
            array[hole] = array[hole/2];
            hole = hole/2;
            numberOfComparisons++;
        }

        array[hole] = x;
    }

    public int findMin() throws Exception{

        if(isEmpty()){
            throw new Exception("Binary Heap is empty!");
        }

        return array[1];
    }

    public int deleteMin() throws Exception{

        int minimum = findMin();
        array[1] = array[currentSize--];
        percolateDown(1);

        return minimum;
    }

    private void buildHeap(){

        for(int i=currentSize/2; i>0; i--){
            percolateDown(i);
        }
    }

    public boolean isEmpty(){
        return currentSize == 0;
    }

    public int size(){
        return currentSize;
    }

    public void makeEmpty(){
        currentSize = 0;
    }

    private void doubleArray(){

        int[] newArray = new int[array.length*2];

        for(int i=0; i<array.length; i++){
            newArray[i] = array[i];
        }

        array = newArray;
    }

    private void percolateDown(int hole){

        int child;
        int temp = array[hole];

        while(hole*2 <= currentSize){

            child = hole*2;

            if(child != currentSize && array[child+1] < array[child]){
                child++;
                //numberOfComparisons++;
            }

            if(array[child] < temp){
                array[hole] = array[child];
                //numberOfComparisons++;
            }
            else{
                break;
            }
            numberOfComparisons++;
            hole = child;
            array[hole] = temp;
        }
    }
} 

public class Heapsort {

    public static void main(String[] args) throws IOException, Exception{


        int[] array = {12, 4, 16, 7, 9, 5, 4, 10, 7, 18, 13, 11, 6, 1, 11};


        System.out.println("Original Array"); 
        printArray(array); 

        heapSort(array); 

        System.out.println("\nSorted array"); 
        printArray(array);

        //System.out.println("\nNumber of Comparisons: " + numberOfComparisons);
    } 

    public static void heapSort(int[] array) throws Exception {

        MinHeap heap = new MinHeap(array.length);

        for(int i=0; i<array.length; i++){
            heap.insert(array[i]);
        }

        for(int i=0; i<array.length; i++){
            array[i] = heap.deleteMin();
        }

        System.out.println("Number of Comparisons: " + heap.numberOfComparisons);
    }

    public static void printArray(int[] array) { 

        for(int i=0; i<array.length; i++){
            System.out.print(array[i] + " "); 
        } 
        System.out.println(); 
    } 

}

Answer 1

    while(hole*2 <= currentSize){

        child = hole*2;

        if(child != currentSize){
            // only and always compare when child != currentSize
            numberOfComparisons++;
            if (array[child+1] < array[child]) {
                child++;
            }
        }

        // array[child] < temp compare always happens
        numberOfComparisons++;
        if(array[child] < temp){
            array[hole] = array[child];
        }
        else{
            break;
        }
        hole = child;
        array[hole] = temp;
    }

请帮忙投票。