java - 排序比较计数器

Question

我有这段代码，可以对填充有随机数的数组进行排序，并计算完成排序所需的数字比较。我正在使用排序方法选择冒泡和合并排序。我有选择和气泡的计数器，但没有合并的计数器，我不知道把它放在哪里。这可能是一个简单的答案，但我就是无法让它发挥作用。

代码:

/***********************************************************************
     * 
     * Selection Sort:
     * Reads in the array and then searches for the largest number. 
     * After it finds the largest number, it then swaps that number with the
     * last number of the array
     * Precondition: takes in an array of "n" items, which in this particular
     * case is 2000, 4000, 6000, 8000, and 10000 random items in an array
     * Postcondition: all numbers are sorted in ascending order
     * 
     **********************************************************************/
    public static int SelectionSort (int[] intArray) {

        //Set initial count of comparisons at 0         
        comparisons= 0;        //Number of swaps made


        for(int last = intArray.length - 1; last > 0; last--) {

            int largestIndex = last;    //Int which places the largest number at the end of the array

            // Find largest number
            for(int i = 0; i < last; i++) {

                //if i > the last number
                if (intArray[i] > intArray[largestIndex]){
                    largestIndex = i;       //switch the last number and i
                } // end if

                //Comparison+1 
                comparisons++;

            } // end for

            // Swap last element with largest element
            int largest = intArray[last];
            intArray[last] = intArray[largestIndex];
            intArray[largestIndex] = largest;

        }
        //Return comparison counter
        return comparisons;
    }

    /***********************************************************************
     * 
     * Bubble Sort:
     * Takes an array of random integers and sorts them by comparing adjacent
     * numbers to one another. Whichever the larger adjacent number, Bubble
     * Sort switches it towards the back end of the adjacent numbers. It does
     * this until the list is fully sorted.
     * Precondition: takes in a random array of integers
     * Postcondition: array is sorted from smallest to largest
     * 
     **********************************************************************/
    public static int BubbleSort (int[] intArray) {

        //Instance Variables    
        int n = intArray.length;
        //boolean swap;   
        comparisons = 0;

        //swap = false;
        //for i starts at 0, when i is less than array length, i++ until reach array length
        for(int i=0; i < n; i++) {

            for(int j=1; j < (n-i); j++) {

                if(intArray[j-1] > intArray[j]) {

                    //Swap the elements
                    int temp = intArray[j];
                    intArray[j] = intArray[j+1];
                    intArray[j+1] = temp;
                    //swap = true;

                } 
            //comparisons get +1 until the for loop is done sorting
            comparisons++;
           }  //End for loop
        }
        //Return the comparison counter
         return comparisons;
    }

    /************************************************************************************
     * 
     * Merge Sort:
     * This method takes a random array and splits it in half. Once the array is
     * split in half, it creates a temp0rary array. This temporary array is built by
     * the method searching the two halves of the original array and puts the information
     * in order stored in the temporary array. Once all the numbers are in order, the 
     * temporary array is then copied back to the original array.
     * Precondition: take in an array of random integers
     * Postcondition: return the random array sorted in ascending order
     * 
     **********************************************************************************/
    public static int mergeSort(int[] intArray) {

        if(intArray.length >= 2) {

            int mid = intArray.length / 2;
            //Create 2 arrays to store half of the data in each
            int[] first = new int[mid];     //holds first half of array
            int[] second = new int[intArray.length - mid];  //holds second half of array

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

            for(int i = 0; i < second.length; i++) {
                second[i] = intArray[mid+i];
            }

            mergeSort(first);
            mergeSort(second);
            merge(first, second, intArray);     //Merge all together

        }

        return comparisons;
    }

    //merging first and second halves of mergeSort array
    public static int merge(int[] first, int[] second, int[] intArray) {

        int iFirst = 0;
        int iSecond = 0;
        int i = 0; 

        //moving the smaller element into intArray
        while(iFirst < first.length && iSecond < second.length) {

            comparisons++;

            if(first[iFirst] < second[iSecond]) {
                intArray[i] = first[iFirst];
                iFirst++;
            }

            else {
                intArray[i] = second[iSecond];
                iSecond++;
            }
            i++;
        }


        //copying the remaining of first array
        while(iFirst < first.length) {
            intArray[i] = first[iFirst];
            iFirst++; i++; 
        }

        //copying the remaining of second array
        while(iSecond < second.length)
        {
            intArray[i] = second[iSecond];
            iSecond++; i++; 
        } 

        return comparisons;
    }

    /**************************************************************************************
     * Instance methods:
     * These methods perform actions to the array.
     * 
     * copyArray()--makes a copy of the array to be used in the main class
     *              so that each method is able to create the same array
     * 
     * printArray()--prints out the array for display
     * 
     * randomArray()--creates a random integer array used by all three sorting methods
     * 
     **************************************************************************************/

    public static int[] copyArray(int[] intArray) {

        //Constructor that creates copyArray
        int[] copyArray = new int[intArray.length];     //siz equal to the length of the array

        for(int i = 0; i < intArray.length; i++){
            copyArray[i] = intArray[i];
        } // end for

        return copyArray;

    } // end copyArray

    //Prints out array
    public static void printArray(int[] intArray){
        //Preconditions
        //  Input: unsorted integer array   
        //  Assumptions: array is full
        //Postconditions
        //  Output: none
        //  Actions: array is displayed on screen

        System.out.print("Array==> ");
        for(int i = 0; i < intArray.length; i++){
            System.out.print(intArray[i] + " ");
        } // end for

        System.out.println(" ");

    } // end printArray

    //Creates a random array that is used for each sorting method
    public static int[] randomArray(int array, double range){
        //Preconditions
        //  Input: size of array(n), range of integers (0 to range)
        //  Assumptions: none
        //Postconditions
        //  Output: array of random integers 0 to floor(range) 
        //  Actions: none

        int[] intArray = new int[array];

        for(int i = 0; i < array; i++){
            intArray[i] = (int)(Math.random() * range);
        } // end for

        return intArray;

    } // end randomIntArray


}

Answer 1

当执行以下几行时(或之前):

• if (intArray[i] > intArray[largestIndex]){
• if(intArray[j-1] > intArray[j]) {
• if(第一[iFirst] < 第二[iSecond]) {

您的 mergeSort 方法使用递归。因此，它需要采用比较参数，并将其传递给每个后续方法调用，并再次接收返回的结果值。

public static int mergeSort(int[] intArray, int comparisons) {

    if(intArray.length >= 2) {

        int mid = intArray.length / 2;
        //Create 2 arrays to store half of the data in each
        int[] first = new int[mid];     //holds first half of array
        int[] second = new int[intArray.length - mid];  //holds second half of array

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

        for(int i = 0; i < second.length; i++) {
            second[i] = intArray[mid+i];
        }

        comparisons = mergeSort(first, comparisons);
        comparisons = mergeSort(second, comparisons);
        comparisons = merge(first, second, intArray, comparisons);     //Merge all together

    }

    return comparisons;
}

//merging first and second halves of mergeSort array
public static int merge(int[] first, int[] second, int[] intArray, int comparisons) {

    int iFirst = 0;
    int iSecond = 0;
    int i = 0; 

    //moving the smaller element into intArray
    while(iFirst < first.length && iSecond < second.length) {

        comparisons++;

        if(first[iFirst] < second[iSecond]) {
            intArray[i] = first[iFirst];
            iFirst++;
        }

        else {
            intArray[i] = second[iSecond];
            iSecond++;
        }
        i++;
    }


    //copying the remaining of first array
    while(iFirst < first.length) {
        intArray[i] = first[iFirst];
        iFirst++; i++; 
    }

    //copying the remaining of second array
    while(iSecond < second.length)
    {
        intArray[i] = second[iSecond];
        iSecond++; i++; 
    } 

    return comparisons;
}