我有这段代码对一个填充了随机数的数组进行排序,并计算完成排序所需的数字比较。我正在使用排序方法选择气泡和合并排序。我有选择和气泡的计数器,但没有合并我不知道把它放在哪里。这可能是一个简单的答案,但我无法让它发挥作用。
代码:
/***********************************************************************
*
* 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
}