Добавление метода сортировки слиянием для случайного массива - PullRequest
Новая
       19

Добавление метода сортировки слиянием для случайного массива

0 голосов
/ 19 марта 2012

Я сделал некоторый код, который генерирует случайный массив и быстро его сортирует.Тем не менее, мне нужно сделать то же самое с алгоритмом сортировки слиянием, но я не уверен, как.Я также проверяю наличие меню, чтобы массив мог быть изолирован для одного вида.Кто-нибудь может опубликовать некоторые идеи о том, как я могу добавить метод сортировки слиянием? 

  import java.util.Scanner;
  import java.util.Random;
  public class Algo {

  public static void main(String[] args) {
  Random gen = new Random();
  Scanner scanner = new Scanner(System.in);
  int[] a = new int[20];

  for (int i = 0; i < a.length; i++)
    a[i] = gen.nextInt(100);

  System.out.println("1. Quick Sort");
  System.out.println("2. Merge Sort");
  System.out.println("what number do you want?");
  int choice = scanner.nextInt();
  if (choice == 1) {
  System.out.println("Quick sort:");
  printArray(a);
  quickSort(a, 0, a.length - 1);
  printArray(a);
  }
  else 
  {
  System.out.println("Merge sort:");
  printArray(a);
  //MERGE SORT NEEDED
  printArray(a);
  }


}

 private static void printArray(int[] a){
  for (int i : a)
    System.out.print(i + " ");
  System.out.println("");
}
private static void quickSort(int a[], int left, int right)
{
  int i = left, j = right;
  int tmp;
  int pivot = a[(left + right) / 2];
  while (i <= j) {
        while (a[i] < pivot)
              i++;
        while (a[j] > pivot)
              j--;
        if (i <= j) {
              tmp = a[i];
              a[i] = a[j];
              a[j] = tmp;
              i++;
              j--;
    }
}
if (left < j)
    quickSort(a, left, j);
if (i < right)
        quickSort(a, i, right);
}
private static void printArrays(int[] a, int tmp){
System.out.println();
for (int x = 0; x < a.length; x++){
System.out.print(tmp);
}
}
}

1 Ответ

0 голосов
/ 19 марта 2012

Вот моя реализация Java для mergesort. Вы можете изменить его при необходимости: 

public class MergeSort
{
public int[] arr;

public MergeSort( int[] a )
{
    arr = a;
}

private void mergeSort( int a, int b )
{
    if( a==b )
        return;

    int mid = ( a+b )/2;
    mergeSort( a, mid );
    mergeSort( mid+1, b );
    merge( a, mid, mid+1, b );
}

public void sort()
{
    mergeSort( 0, arr.length-1 );
}

private void merge( int a, int m1, int m2, int b )
{
    int[] sorted = new int[ b-a+1 ];
    int i=0, j=0;

    while( ( i<(m1-a+1)) &&( j<( b-m2+1 )) )
    {
        if( arr[ a+i ] < arr[ a+j ])
        {
            sorted[ i+j ] = arr[ a+i ];
            i++;
        }

        else
        {
            sorted[ i+j ] = arr[ a+j ];
            j++;
        }

    }

    // copy rest of the remaining array

    while( i< (m1-a+1 ))
    {
        sorted[ i+j ] = arr[ a+i ];
        i++;
    }

    while( j<( b-m2+1 ))
    {
        sorted[ i+j ] = arr[ a+j ];
        j++;
    }
    System.arraycopy(sorted, 0, arr, a, b - a + 1);
}


}
...