Fusionner Trier en Java ne fonctionne pas comme prévu. Essayer de le faire sans boucle while

Question

J'ai travaillé dessus toute la journée et je ne sais pas pourquoi cela ne fonctionne pas. Le tri est en train de dupliquer certains éléments et de trier certains éléments du tableau, mais je ne vois pas ce qui en est la cause. Je ai essayé de le tracer, mais je ne pouvais pas le suivre.

import java.io.FileNotFoundException; 
import java.util.Arrays; 
public class Main { 
    public static void main(String[] args) throws FileNotFoundException { 

     int[] array = new int[10]; 
     for(int i = 0; i < array.length; i++) { 
      array[i] = (int) (Math.random()*5); 
     } 

     int[] temp = array.clone(); 
     int l = 0; 
     int r = array.length-1; 
     System.out.println("unsorted "+Arrays.toString(array)); 
     mergeSort(array, temp, l, r); 
     System.out.println("sorted "+Arrays.toString(array)); 
    } 

    public static void mergeSort(int[] array, int[] temp, int p, int r) { 
     int q = (p + r)/2; 
     if(p < r) { 
      mergeSort(array, temp, p, q); 
      mergeSort(array, temp, q+1, r); 
      merge(array, temp, p, q, r); 
     } 
    } 

    public static void merge(int[] array, int[] temp, int p, int q, int r) { 


     int i = p; 
     int j = q + 1; 

     for(int k = p; k < r; k++){ 
     if(i > q){ 
      array[k] = temp[j]; 
      j++; 
     } else if(j > r) { 
      array[k] = temp[i]; 
      i++; 
     } 
     else if(temp[j] < temp[i]) { 
      array[k] = temp[j]; 
      j++; 
     } else { 
      array[k] = temp[i]; 
      i++; 
     } 
     } 
    } 
} 

Answer 1

Votre code a deux problèmes:

1. Votre boucle for doit être compris r car il est le dernier indice:

   for(int k = p; k <= r; k++) 
   

2. Vous devez retransférer sur temp à la fin de votre opération de fusion:

   for (int k = p; k <= r; k++) { 
       temp[ k ] = array[ k ]; 
   } 
   

   ou:

   System.arraycopy(array, p, temp, p, r + 1 - p);