tas de tri fonction explication nécessaire

Question

Quelqu'un peut-il m'expliquer clairement comment fonctionnent ces fonctions de tri de tas?

void heapSort(int numbers[], int array_size) 
{ 
    int i, temp; 

    for (i = (array_size/2)-1; i >= 0; i--) 
    siftDown(numbers, i, array_size); 

    for (i = array_size-1; i >= 1; i--) 
    { 
    temp = numbers[0]; 
    numbers[0] = numbers[i]; 
    numbers[i] = temp; 
    siftDown(numbers, 0, i-1); 
    } 
} 


void siftDown(int numbers[], int root, int bottom) 
{ 
    int done, maxChild, temp; 

    done = 0; 
    while ((root*2 <= bottom) && (!done)) 
    { 
    if (root*2 == bottom) 
     maxChild = root * 2; 
    else if (numbers[root * 2] > numbers[root * 2 + 1]) 
     maxChild = root * 2; 
    else 
     maxChild = root * 2 + 1; 

    if (numbers[root] < numbers[maxChild]) 
    { 
     temp = numbers[root]; 
     numbers[root] = numbers[maxChild]; 
     numbers[maxChild] = temp; 
     root = maxChild; 
    } 
    else 
     done = 1; 
    } 
} 

Answer 1

This page a de nombreuses explications avec des diagrammes sur le tri de tas. Cela peut aider à considérer cela comme un tournoi: d'abord, vous insérez tous les joueurs de telle sorte que le meilleur joueur est le gagnant. Ensuite, vous extrayez le gagnant, faites la promotion d'un perdant en tant que nouveau gagnant, et effectuez des ajustements pour que vous obteniez à nouveau un bon tournoi, le nouveau gagnant étant le meilleur des joueurs restants.

Ensuite, vous itérez.

Answer 2

public class heapsort 
{ 


public static void buildheap(int[] a, int nextLimit) 
{ 
    // for parent 3 child is 3*2+1=7 and 3*2+2=8 hence parent if odd n+1/2-1 i.e (7+1)/2-1=3 for odd n/2-1 8/2-1=3 
    int child = nextLimit % 2 == 1 ? nextLimit + 1 : nextLimit; 
    for (int parent = child/2 - 1; parent >= 0; parent--) { 
     heapfy(a, parent, nextLimit); 
    } 


} 

public static void heapfy(int[] a, int parentIndex, int limit) 
{ 
    int maxChildIndex; 
    //if parent have only one child (java array index start from 0 hence left one 2i+1 and right one 2i+2) 
    if ((2 * parentIndex + 2) > limit) { 
     maxChildIndex = 2 * parentIndex + 1; 
    } else { 
     //find max value index from two child 
     maxChildIndex = a[2 * parentIndex + 1] > a[2 * parentIndex + 2] ? 2 * parentIndex + 1 : 2 * parentIndex + 2; 
    } 


    //swap if parent less than max child bring max value to parent 
    if (a[maxChildIndex] > a[parentIndex]) { 

     int maxValue = a[maxChildIndex]; 
     a[maxChildIndex] = a[parentIndex]; 
     a[parentIndex] = maxValue; 

    } 


} 


public static void main(String[] args) 
{ 
    int[] a = {2, 5, 4, 6, 77, 3, 1, 8}; 
    for (int nextArrayLength = a.length - 1; nextArrayLength >= 0; nextArrayLength--) { 
     buildheap(a, nextArrayLength); 

     //push to first to last 
     int highest = a[0]; 
     a[0] = a[nextArrayLength]; 
     a[nextArrayLength] = highest; 
    } 


    for (int i = 0; i < a.length; i++) { 


     System.out.println(a[i]); 
    } 


} 

}