JavaScript-Blasensortierungsalgorithmus

Via Bubble Sort ist oft der erste Sortieralgorithmus, an den die Leute denken, weil er relativ einfach und leicht zu verstehen ist. Die Grundidee besteht darin, zwei Zahlen gleichzeitig zu vergleichen und sicherzustellen, dass sie in der richtigen Reihenfolge sind, bevor mit anderen Elementen fortgefahren wird. Am Ende jedes Levels werden die wertvollen Gegenstände an ihre richtigen Positionen „sortiert“, so dass am Ende nur noch andere Gegenstände zum Sortieren übrig bleiben. Originaltext von: http://caibaojian.com/javascript-bubble-sort.html

Ideen zur Algorithmusimplementierung

Vergleichen Sie das erste und das zweite Element

Wenn das erste The Artikel sollte nach dem zweiten Artikel sein, tauschen Sie sie aus

Vergleichen Sie den zweiten und dritten Artikel

Wenn der zweite Artikel nach dem dritten Artikel sein sollte, tauschen Sie sie aus

Fahren Sie fort, bis der Ende der Daten

Dieser Vorgang wird mehrmals wiederholt, bis die Daten vollständig sortiert sind. Da das letzte Element jedes Mal korrekt sortiert ist, müssen immer weniger Elemente sortiert werden. Vergleichen wir zum besseren Verständnis ein Array: [3, 2, 4, 5, 1].

Beispiel für einen Vergleichsprozess

Das erste ist die positive Sortierung, bei der das erste Element mit dem zweiten verglichen wird Element, da 2 kleiner als 3 ist, steht 3 also an letzter Stelle und das Ergebnis ist [2,3,4,5,1].

Die Reihenfolge des zweiten und dritten Elements ist korrekt, keine Notwendigkeit Austausch; der dritte und vierte Artikel sind ebenfalls korrekt, kein Austausch erforderlich, der vierte und fünfte Artikel werden ausgetauscht, das Ergebnis ist [2,3,4,1,5].

Schleifen Sie den ersten Artikel erneut Und der zweite Artikel wiederum tauscht den dritten und vierten Artikel aus, also [2,3,1,4,5]

Im dritten Zyklus werden der zweite und dritte Artikel als [2,1 ,3,4,5]

Für den vierten Zyklus sind der erste und der zweite Austausch [1,2,3,4,5]

Der erste Schritt zur Implementierung der Blasensortierung Es ist um eine Methode zum Austauschen zweier Elemente im Array zu erstellen. Diese Methode ist bei vielen ineffizienten Sortierungen relativ häufig. Ein einfacher Javascript-Implementierungscode lautet:

function swap(items, firstIndex, secondIndex){
    var temp = items[firstIndex];
    items[firstIndex] = items[secondIndex];
    items[secondIndex] = temp;
}

via Wie oben erwähnt, ist dieser Sortieralgorithmus relativ ineffizient, da er mehrere Sortierungen erfordert. Angenommen, ein Array hat n Elemente, dann ist für die Berechnung 2 hoch n-te Potenz erforderlich. Schauen wir uns diesen Originaltext an: http://caibaojian.com/javascript-bubble-sort.html

Positive Directional Bubbling-Algorithmus

function bubbleSort(items){

    var len = items.length,
        i, j, stop;

    for (i=0; i < len; i++){
        for (j=0, stop=len-i; j < stop; j++){
            if (items[j] > items[j+1]){
                swap(items, j, j+1);
            }
        }
    }

    return items;
}

via Die äußere Schleife steuert die Anzahl der Schleifenzyklen und die innere Schleife ist der Sortiervergleich zwischen Elementen.

Reverse Bubble Sort

function bubbleSort(items){
    var len = items.length,
        i, j;

    for (i=len-1; i >= 0; i--){
        for (j=len-i; j >= 0; j--){
            if (items[j] < items[j-1]){
                swap(items, j, j-1);
            }
        }
    }

    return items;
}

via Die Ergebnisse der beiden oben genannten Codes sind gleich, sie werden von klein nach groß sortiert, aber die Reihenfolge der Schleife ist etwas unterschiedlich, beide sind es Blasen positiver Ordnung Blase.

Umgekehrte Blasensortierung

In der Tat geht es darum, die Größenänderung zu beurteilen. Wenn das erste Element kleiner als das zweite Element ist, werden die Positionen getauscht.

function bubbleSort2(items){
var len = items.length,
i,j,stop;
for(i=0;i<len; i++){
for(j=0,stop=len-i;j<stop;j++){
if(items[j]<items[j+1]){
swap(items,j,j+1);
}
}
}
return items;
}

Zusammenfassung

via Auch hier ist die Blasensortierung möglicherweise nicht auf Ihre tatsächliche Arbeit anwendbar. Es handelt sich lediglich um ein einfaches Tool, das uns hilft, den Algorithmus zu verstehen und den Grundstein zu legen für mehr Wissen. Am häufigsten verwenden wir wahrscheinlich die integrierte Prototypmethode Array.prototype.sort(), da sie effizienter ist.

Weitere Artikel zum JavaScript-Blasensortierungsalgorithmus finden Sie auf der chinesischen PHP-Website!