Heim > Web-Frontend > js-Tutorial > Ausführliche Erklärung der Bucket-Sortierung in JavaScript

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

韦小宝
Freigeben: 2018-03-14 14:28:37
Original
2712 Leute haben es durchsucht

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:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

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

Nach dem Login kopieren

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!

Verwandte Etiketten:
Quelle:php.cn
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage