2015-10-30 14 views
6

che sto tentando di scrivere un metodo heapsort in Java, ma non funziona esattamente come voglio che:Cosa c'è di sbagliato nel mio codice HeapSort?

public class HeapSort { 

    private static int n; 

    private static void swap(int[] A, int a, int b) 
    { 
     int tmp = A[a]; 
     A[a] = A[b]; 
     A[b] = tmp; 
    } 

    private static void insert(int[] A, int i) 
    { 
     int left = i * 2; 
     int right = left + 1; 
     int max = i; 

     if (left <= n && A[left] < A[max]){ 
      max = left; 
     } 
     if (right <= n && A[right] > A[max]) { 
      max = right; 
     } 
     if (max != i) { 
      swap(A, i, max); 
      insert(A, max); 
     } 
    } 

    public static void HeapSort(int[] A) 
    { 
     n = A.length - 1; 

     for (int i = n/2; i >= 0; i--) 
      insert(A, i); 

     for (int i = n; i > 0; i--) { 
      swap(A, 0, i); 
      n--; 
      insert(A, 0); 
     } 
    } 

    public static void main(String[] args){ 
     int[] A = new int[] {9, 2, 8, 1, 4}; 
     System.out.println(java.util.Arrays.toString(arr)); 
     HeapSort(A); 
     System.out.println(java.util.Arrays.toString(arr)); 
    } 
} 

Funziona con alcuni array tuttavia array come 9, 2, 8, 1, 4 otterrà ordinati in 1, 4, 2, 8, 9. Allora perché non ordina l'array nel modo corretto?

risposta

1
if (left <= n && A[left] > A[i]){ 
    max = left; 
} 

Prova questo e guarda. Ho fatto il programma completo come sotto. Funziona bene per l'input che hai fornito.

public class HeapSort { 

private static int n; 

private static void swap(int[] A, int a, int b) 
{ 
    int tmp = A[a]; 
    A[a] = A[b]; 
    A[b] = tmp; 
} 

private static void insert(int[] A, int i) 
{ 
    int left = i * 2; 
    int right = left + 1; 
    int max = i; 

    if (left <= n && A[left] > A[i]){ 
     max = left; 
    } 
    if (right <= n && A[right] > A[max]) { 
     max = right; 
    } 
    if (max != i) { 
     swap(A, i, max); 
     insert(A, max); 
    } 
} 

public static void HeapSort(int[] A) 
{ 
    n = A.length - 1; 

    for (int i = n/2; i >= 0; i--) 
     insert(A, i); 

    for (int i = n; i > 0; i--) { 
     swap(A, 0, i); 
     n--; 
     insert(A, 0); 
    } 
} 

public static void main(String[] args){ 
    int[] A = new int[] {19, 6, 28, 1, 0}; 
    int[] B = new int[] {1, 2, 4, 8, 9, 0}; 
    System.out.println(java.util.Arrays.toString(A)); 
    System.out.println(java.util.Arrays.toString(B)); 
    HeapSort(A); 
    HeapSort(B); 
    System.out.println(java.util.Arrays.toString(A)); 
    System.out.println(java.util.Arrays.toString(B)); 
} 

}

Ecco l'output.

[19, 6, 28, 1, 0] 
[1, 2, 4, 8, 9, 0] 
[0, 1, 6, 19, 28] 
[0, 1, 2, 4, 8, 9] 
+0

Sta funzionando per 9, 2, 8, 1, 4 ma non ha funzionato per 19, 6, 28, 1, 0. Ha restituito 0, 1, 6, 28, 19. Quindi, perché no? swap 28 e 19? –

+0

Ok, il codice aggiornato funziona ora. Tutto quello che mi chiedo è quale sia il tempo di esecuzione. –

0

Se si definisce left = i * 2, la radice del tuo mucchio devono essere conservati in A[1], non A[0]. Non utilizzando la matrice nell'indice 0, è sempre possibile affermare che i figli destro e sinistro di un nodo i sono 2*i e 2*i+1, rispettivamente.

Fondamentalmente, nel tuo HeapSort, devi cambiare da 0 a 1 (ce ne sono 4). Provalo con l'array {0, 9, 2, 8, 1, 4}.

E inoltre, un confronto in insert è anche sbagliato. Dovrebbe essere A[left] > A[max].

+0

Funziona per 9, 2, 8, 1, 4 ma per 0, 9, 2, 8, 1, 4 lo restituisce come 1, 2, 4, 8, 9, 0. Perché lo fa? –

Problemi correlati