Я сделал сортировку слиянием, которая сопоставляется с двумя уже созданными сортировками выбора и вставки, которые подсчитывают сравнение, так что при выполнении программа показывает, какие методы быстрее.
- Я не могувыяснить, как реализовать подсчет в моем наборе слияний
- Я действительно не знаю, работает ли он вообще правильно или я просто отображаю ранее отсортированный массив, который был отсортирован путем выделения или вставки над ним,Я думаю, что это потому, что я не смог назвать метод, как выбор и вставка.(Вы увидите ниже)
Пока я выложу полный код, чтобы вы могли видеть выделение и вставку, как они использовались.
Arraysort.java
public class ArraySort {
private long[] a; // ref to array a
private int nElems; // number of data items
public ArraySort(int max) // constructor
{
a = new long[max]; // create the array
nElems = 0; // no items yet
}
public void Clone(ArraySort c) // c is another array
{
c.nElems = this.nElems; // Copy nElems
System.arraycopy(this.a, 0, c.a, 0, this.nElems); // Copy elements
}
public void insert(long value) // put element into array
{
a[nElems++] = value; // insert value
}
public String toString() // displays array contents
{
String res="";
for(int j=0; j<nElems; j++) // for each element,
res = res + a[j] + " "; // append it to res
return res;
}
private int insertOrder(int n, long temp) { // insert temp into a[0..(n-1)]
// and keep a[0..n] sorted.
int count = 0;
while (n>0) {
count++; // count next comparison
if (a[n-1] > temp) { // until one is smaller,
a[n] = a[n-1]; // shift item to right
--n; // go left one position
} else break;
}
a[n] = temp; // insert marked item
return count;
}
public int insertionSort() {
int count = 0;
for (int n=1; n<nElems; n++)
count += insertOrder(n, a[n]); // insert a[n] into a[0..(n-1)]
return count;
} // end insertionSort()
private void swap(int one, int two) {
long temp = a[one];
a[one] = a[two];
a[two] = temp;
}
public int selectionSort() {
int out, in, max, count=0;
for(out=nElems-1; out > 0; out--) { // outer loop
max = out; // max is maximum item's index
for(in=0; in<out; in++) { // inner loop
if(a[in] > a[max] ) // if max is smaller,
max = in; // we have a new max
count++; // count one comparison
}
swap(out, max); // swap them
} // end for(out)
return count;
} // end selectionSort()
public void mergeSort() {
long[] ws = new long[nElems];
recMergeSort(ws, 0, nElems-1);
}
public void recMergeSort(long[] ws, int lower, int upper) {
if (lower == upper)
return;
else {
int mid = (lower + upper) / 2; //find midpoint
recMergeSort(ws, lower, mid); //sort lower
recMergeSort(ws, mid+1, upper); //sort upper
merge(ws, lower, mid+1, upper); //merge
}
}
public void merge(long[] ws, int lowPtr, int highPtr, int upper) {
int j = 0;
int lower = lowPtr;
int mid = highPtr-1;
int n = upper-lower+1; //# of items
while(lowPtr <= mid && highPtr <= upper)
if( a[lowPtr] < a[highPtr] )
ws[j++] = (int) a[lowPtr++];
else
ws[j++] = (int) a[highPtr++];
while(lowPtr <= mid)
ws[j++] = (int) a[lowPtr++];
while(highPtr <= upper)
ws[j++] = (int) a[highPtr++];
for(j=0; j<n; j++)
a[lower+j] = ws[j];
}
public void display() {
for(int j=0; j<nElems; j++) {
System.out.print(a[j] + " "); }
System.out.println("");
}
//end
}
SortComparison.java
import java.util.*;
public class SortComparison {
public static void main(String[] args) {
int count, maxSize = 100; // array size
ArraySort arr, carr; // reference to array
arr = new ArraySort(maxSize); // create the arrays
carr = new ArraySort(maxSize);
// insert some random numbers
Random generator = new Random();
for (int i = 0; i < 20; i++) {
arr.insert(Math.abs(generator.nextInt())%maxSize);
}
System.out.println("Before sort: " + arr); // display items
arr.Clone(carr);
count = carr.insertionSort(); // insertion-sort a clone of arr
System.out.println("\nInsert sort: \n" + carr + " ### Comparisons: " + count);
arr.Clone(carr);
count = carr.selectionSort(); // selection-sort a clone of arr
System.out.println("\nSelect sort: \n" + carr + " ### Comparisons: " + count);
carr.mergeSort();
System.out.println("\nMerge sort: ");
carr.display();
}
}
Вы можете видеть, как должны вызываться вещи, с возвратом счетчика, путем выбора и вставки ..