Maison >interface Web >js tutoriel >Explication détaillée du tri par tas en JavaScript

Explication détaillée du tri par tas en JavaScript

韦小宝
韦小宝original
2018-03-14 14:22:192128parcourir

Cet article parle du tri par tas en JavaScript. Si vous ne connaissez pas le tri par tas en JavaScript ou si vous êtes intéressé par le tri par tas en JavaScript, jetons un coup d'œil à cet article. Bon, assez de bêtises. point

Le tri par tas peut être considéré comme un tri par sélection qui utilise le concept de tas pour trier. Divisé en deux méthodes :

1, Big top tas : La valeur de chaque nœud est supérieure ou égale à la valeur de son nœud enfant, utilisée par ordre croissant dans l'algorithme de tri du tas

2. Petit tas supérieur : La valeur de chaque nœud est inférieure ou égale à la valeur de son nœud enfant, utilisée par ordre décroissant dans l'algorithme de tri du tas

Démonstration d'animation de tri par tas

Explication détaillée du tri par tas en JavaScript

Implémentation du code JavaScript :

var len;    //因为声明的多个函数都需要数据长度,所以把len设置成为全局变量function buildMaxHeap(arr) {   //建立大顶堆  
    len = arr.length;  
    for (var i = Math.floor(len/2); i >= 0; i--) {  
        heapify(arr, i);  
    }}function heapify(arr, i) {     //堆调整  
    var left = 2 * i + 1,  
        right = 2 * i + 2,  
        largest = i;  
  
    if (left < len && arr[left] > arr[largest]) {  
        largest = left;  
    }  
  
    if (right < len && arr[right] > arr[largest]) {  
        largest = right;  
    }  
  
    if (largest != i) {  
        swap(arr, i, largest);  
        heapify(arr, largest);  
    }}function swap(arr, i, j) {  
    var temp = arr[i];  
    arr[i] = arr[j];  
    arr[j] = temp;}function heapSort(arr) {  
    buildMaxHeap(arr);  
  
    for (var i = arr.length-1; i > 0; i--) {  
        swap(arr, 0, i);  
        len--;  
        heapify(arr, 0);  
    }  
    return arr;}

Ce qui précède représente tout le contenu de cet article. à ce sujet, vous pouvez le mettre en œuvre vous-même. Il est facile de maîtriser les deux côtés !

Recommandations associées :

JavascriptTri par tasExplication détaillée de l'algorithme

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn