爲隨機數組添加合併排序方法

Question

我做了一些代碼，生成一個隨機數組並通過快速排序。不過，我需要對合並排序算法做同樣的事情，但我不知道如何。我也確保有一個菜單，以便數組可以隔離一種。任何人都可以發表一些關於如何添加合併排序方法的想法？

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

Answer 1

這裏是我的歸併Java實現。您可以根據需要進行修改：

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


}