Ausführliche Erklärung der Bucket-Sortierung in JavaScript

In diesem Artikel geht es um die Bucket-Sortierung in JavaScript Wenn Sie sich mit der Bucket-Sortierung in JavaScript nicht auskennen, schauen wir uns diesen Artikel an Machen Sie Schluss mit dem Unsinn und kommen Sie auf den Punkt

Eimersortierung ist eine verbesserte Version der Zählsortierung. Es nutzt die Abbildungsbeziehung der -Funktion . Der Schlüssel zur Effizienz liegt in der Bestimmung dieser Abbildungsfunktion.

Um die Eimersortierung effizienter zu gestalten, müssen wir diese beiden Dinge tun:

1 Wenn genügend zusätzlicher Platz vorhanden ist, versuchen Sie, die Anzahl der Eimer zu erhöhen

2. Die verwendete Zuordnungsfunktion kann die eingegebenen N-Daten gleichmäßig auf K Buckets verteilen

Gleichzeitig für die Sortierung der Elemente im Bucket, was Welche Vergleichsart soll gewählt werden? Der Sortieralgorithmus hat einen entscheidenden Einfluss auf die Leistung.

Was ist die schnellste Zeit?

Wenn die Eingabedaten gleichmäßig auf jeden Bucket verteilt werden können

Wann ist es am langsamsten?

Wenn die Eingabedaten demselben Bucket zugeordnet werden

JavaScript-Code-Implementierung für Bucket-Sortierung:

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;}

Das Obige ist der gesamte Inhalt dieses Artikels. Wenn Sie nicht viel darüber wissen, können Sie beide Seiten problemlos selbst meistern!

Verwandte Empfehlungen:
PHP-Bucket-Sort-Algorithmus-Implementierungsbeispiel-Sharing

Das obige ist der detaillierte Inhalt vonAusführliche Erklärung der Bucket-Sortierung in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!