Explication détaillée du tri des buckets en JavaScript

Cet article parle du tri par bucket en JavaScript Si vous ne connaissez pas le tri par bucket en JavaScript ou si vous êtes intéressé par le tri par bucket en JavaScript, jetons un coup d'œil à cet article. Arrêtez les bêtises et allez droit au but

Le tri par seau est une version améliorée du tri par comptage. Il utilise la relation de cartographie de la fonction . La clé de l'efficacité réside dans la détermination de cette fonction de cartographie.

Afin de rendre le tri des seaux plus efficace, nous devons faire ces deux choses :

1 Lorsqu'il y a suffisamment d'espace supplémentaire, essayez d'augmenter le nombre de seaux

2. La fonction de cartographie utilisée peut répartir uniformément les N données d'entrée dans K buckets

En même temps, pour le tri des éléments dans le bucket, quoi type de comparaison doit-il être sélectionné ? Les algorithmes de tri ont-ils un impact critique sur les performances.

Quel est le temps le plus rapide

Lorsque les données d'entrée peuvent être réparties uniformément dans chaque compartiment

Quand est-ce le plus lent ?

Lorsque les données d'entrée sont allouées au même bucket

Implémentation du code JavaScript de tri des buckets :

function bucketSort(arr, bucketSize) {  
    if (arr.length === 0) {  
      return arr;  
    }  
  
    var i;  
    var minValue = arr[0];  
    var maxValue = arr[0];  
    for (i = 1; i < arr.length; i++) {  
      if (arr[i] < minValue) {  
          minValue = arr[i];                //输入数据的最小值  
      } else if (arr[i] > maxValue) {  
          maxValue = arr[i];                //输入数据的最大值  
      }  
    }  
  
    //桶的初始化  
    var DEFAULT_BUCKET_SIZE = 5;            //设置桶的默认数量为5  
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;  
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;     
    var buckets = new Array(bucketCount);  
    for (i = 0; i < buckets.length; i++) {  
        buckets[i] = [];  
    }  
  
    //利用映射函数将数据分配到各个桶中  
    for (i = 0; i < arr.length; i++) {  
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);  
    }  
  
    arr.length = 0;  
    for (i = 0; i < buckets.length; i++) {  
        insertionSort(buckets[i]);                      //对每个桶进行排序，这里使用了插入排序  
        for (var j = 0; j < buckets[i].length; j++) {  
            arr.push(buckets[i][j]);                        
        }  
    }  
  
    return arr;}

Ce qui précède représente tout le contenu de cet article. Si vous n'y connaissez pas grand-chose, vous pouvez facilement maîtriser les deux côtés par vous-même !

Recommandations associées :
Implémentation PHP du partage d'exemples d'algorithme de tri de seaux

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!