# 排序比较计数器[英] Sort Comparisons Counter

### 问题描述

```/***********************************************************************
*
* 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

}
```

## 推荐答案

• if (intArray[i] > intArray[largestIndex]){
• if(intArray[j-1] > intArray[j]) {
• if(first[iFirst] < second[iSecond]) {

```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;
}
```