在java中使用heapsort排序

Question

import java.util.Arrays; 

public class Test{ 

//main method 
public static void main(String... args){ 
    int[] a = new int[]{16,14,10,8,7,9,3,2,4,1}; 

    System.out.println("unsorted array " + Arrays.toString(a)); 

    heap_sort(a); 

    System.out.println("Sorted array " + Arrays.toString(a)); 
} 

//returns left child index of given index 
private static int left_child(int i){ 
return (i * 2 + 1); 
} 

//returns right child index of the given index 
private static int right_child(int i){ 
    return (i * 2 + 2); 
} 


public static void max_heapify(int[] array , int index , int heap_size){ 
    int largest = index; 
    int left = left_child(index); 
    int right = right_child(index); 

    if(left < heap_size && array[left] > array[index]){ 
     largest = left; 
    } 
    else largest = index; 

    if (right < heap_size && array[right] > array[largest]){ 
     largest = right; 
    } 

    if(largest != index){ 
     //exchange array[index] with array[largest] 
     int a = array[index]; 
     array[index] = array[largest]; 
     array[largest] = a; 

     max_heapify(array,largest,heap_size); 
    } 
} 

public static void build_max_heap(int[] array){ 
    int heap_size = array.length - 1; 


    for (int i = ((array.length - 1)/2) ; i >= 0 ; i--){ 
     max_heapify(array, i, heap_size); 
    } 
} 

//main heap sort function 
public static void heap_sort(int[] array){ 

    int heap_size = array.length - 1; 


    build_max_heap(array); 

    for(int i = (array.length - 1) ; i > 0 ; i--){ 
     //exchange array[0] with array[i] 
     int a = array[0]; 
     array[0] = array[i]; 
     array[i] = a; 

     heap_size = heap_size - 1; 
     max_heapify(array , 1 , heap_size); 
    } 
} 


} 

我已經嘗試了幾乎所有的可能性，但它不能正常工作。你能找出我錯在哪裏。我的代碼輸出爲： 未排序數組[16,14,10,8,7,9,3,2,4,1] 排序數組[14,10,8,7,9,3,2,4 ，1，16]

Answer 1

的問題是，你失去的項目由於左，右孩子必須是：

//returns left child index of given index 
private static int left_child(int i){ 
return (i * 2); 
} 

//returns right child index of the given index 
private static int right_child(int i){ 
    return (i * 2 + 1); 
} 

Answer 2

存在一些問題： - 左，右孩子被修改，因爲你失去第一數組中的元素。 - 在max_heapify函數中，循環爲< = - 在heap_sort函數中，必須將0而不是1傳遞給max_heapify函數。

//returns left child index of given index 
    private static int left_child(int i) 
    { 
     return (i * 2); 
    } 

    //returns right child index of the given index 
    private static int right_child(int i) 
    { 
     return (i * 2 + 1); 
    } 

    public static void max_heapify(int[] array, int index, int heap_size) 
    { 
     int largest = index; 
     int left = left_child(index); 
     int right = right_child(index); 

     if (left <= heap_size && array[left] > array[index]) 
     { 
      largest = left; 
     } 

     if (right <= heap_size && array[right] > array[largest]) 
     { 
      largest = right; 
     } 

     if (largest != index) 
     { 
      //exchange array[index] with array[largest] 
      int a = array[index]; 
      array[index] = array[largest]; 
      array[largest] = a; 

      max_heapify(array, largest, heap_size); 
     } 
    } 

    public static void build_max_heap(int[] array) 
    { 
     int heap_size = array.length - 1; 


     for (int i = ((array.length - 1)/2); i >= 0; i--) 
     { 
      max_heapify(array, i, heap_size); 
     } 
    } 

    //main heap sort function 
    public static void heap_sort(int[] array) 
    { 

     int heap_size = array.Length - 1; 


     build_max_heap(array); 

     for (int i = (array.Length - 1); i > 0; i--) 
     { 
      //exchange array[0] with array[i] 
      int a = array[0]; 
      array[0] = array[i]; 
      array[i] = a; 

      heap_size = heap_size - 1; 
      max_heapify(array, 0, heap_size); 
     } 
    }