Maison  >  Article  >  interface Web  >  Explication détaillée du tri par base en JavaScript

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

韦小宝
韦小宝original
2018-03-14 14:33:032277parcourir

Cet article parle du tri par base en JavaScript Si vous ne connaissez pas le tri par base en JavaScript ou si vous êtes intéressé par le tri par base en JavaScript, alors jetons un coup d'œil à cet article. dire des bêtises et aller droit au but

Il existe deux méthodes de tri de base

1. Tris MSD d'ordre élevé

2. Le LSD trie à partir de l'ordre le plus bas

Tri Radix vs tri par comptage vs tri par seau


Ces trois algorithmes de tri utilisent tous le concept de seaux. il existe des différences évidentes dans l'utilisation des buckets :

Tri radical : Allouez les buckets en fonction de chaque chiffre de la valeur clé

Tri par comptage : Chaque bucket ne stocke qu'une seule valeur clé

Tri des buckets : chaque bucket stocke une certaine plage de valeurs

Démonstration d'animation de tri par base LSD :

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

Implémentation du code JavaScript de tri Radix :

//LSD Radix Sort  
var counter = [];function radixSort(arr, maxDigit) {  
    var mod = 10;  
    var dev = 1;  
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {  
        for(var j = 0; j < arr.length; j++) {  
            var bucket = parseInt((arr[j] % mod) / dev);  
            if(counter[bucket]==null) {  
                counter[bucket] = [];  
            }  
            counter[bucket].push(arr[j]);  
        }  
        var pos = 0;  
        for(var j = 0; j < counter.length; j++) {  
            var value = null;  
            if(counter[j]!=null) {  
                while ((value = counter[j].shift()) != null) {  
                      arr[pos++] = value;  
                }  
          }  
        }  
    }  
    return arr;}

Ce qui précède est tout le contenu de cet article. Si vous n'y connaissez pas grand-chose, vous pouvez facilement implémenter les deux côtés en. vous-même.

Recommandations associées :

Exemples d'algorithmes de tri par comptage et de tri par base implémentés dans JS

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