Сортировка на Java с «Разделить и покорить»

Question

Объединить сортировку, сортируя, разделив случайный массив пополам и затем поместив их в числовой порядок. Концепция называется «Разделить и покорить». Выход не работает, и я не вижу ничего плохого в этом коде. Main просто выводит все числа в массиве. FYI, другие части кода не проблема. Но если вам это нужно, я могу отдать его вам.

private void merge(int[] a, int first, int mid, int last) 
{ 
    int size = last - first + 1; 
    int [] temp = new int[size]; 
    int i = first, j = mid + 1; 
    for(int s = 0; s < size; s++){ // a.length 
     if(i > mid){ // case a 
      temp[s] = a[j]; 
      j++; 
     }else if(j > last){ // case b 
      temp[s] = a[i]; 
      i++; 
     }else if(a[i] < a[j]){ // case c 
      temp[s] = a[i]; 
      i++; 
     }else if(a[j] <= a[i]){ // case d 
      temp[s] = a[j]; 
      j++; 
     } 
    } 

    for(int s = first; s < size; s++){ 
     a[first] = temp[s - first]; 
    } 
} 

public void mergeSort(int[] a, int first, int last) 
{ 
    int size = last - first + 1, mid; 
    if(size == 1){ 
     steps++; 
    }else if(size == 2){ 
     if(a[last] > a[first]){ 
      int temp = a[last]; 
      a[last] = a[first]; 
      a[first] = temp; 
      steps += 3; 
     } 
    }else{ 
     mid = (last + first)/2; 
     mergeSort(a, first, mid); 
     mergeSort(a, mid + 1, last); 
     merge(a, first, mid, last); 
     steps += 4; 
    } 
} 

Это то, что генератор выглядит следующим образом:

private void fillArray(int numInts, int largestInt) 
{ 
    myArray = new int[numInts]; 
    Random randGen = new Random(); 

    for(int loop = 0; loop < myArray.length; loop++){ 
     myArray[loop] = randGen.nextInt(largestInt) + 1; 
    } 
} 

Answer 1

есть два недостатка в вашем коде:

первые:

for(int s = first; s - first < size; s++){// replace s<size with s-first<size 
     a[s] = temp[s - first];//yours a[first] = temp[s-first] 
} 

в вашем коде, первый является исправлено, и он всегда будет обновлять [первый], который, я думаю, не является тем, что вы хотеть.

второй:

.... 
}else if(a[i] > a[j]){ // case c yours a[i]<a[j] 
      temp[s] = a[i]; 
      i++; 
}else if(a[i] <= a[j]){ // case d yours a[j] <= a[i] 
      temp[s] = a[j]; 
      j++; 
} 
.... 

, потому что о своем роде, вы получите DESCEND последовательность и слияния вы хотите получить Ascend заказ, этот конфликт друг с другом.