Heim > Web-Frontend > js-Tutorial > Hauptteil

js grundlegender Algorithmus: Blasensortierung, binäre Suche

高洛峰
Freigeben: 2016-10-08 17:51:06
Original
1350 Leute haben es durchsucht

Wissenserweiterung:

Zeitkomplexität: Die Zeitkomplexität eines Algorithmus ist eine Funktion, die die Laufzeit des Algorithmus beschreibt. Je geringer die Zeitkomplexität, desto höher die Effizienz.

Selbstverständnis: Die Zeitkomplexität eines Algorithmus wird durch mehrmalige Ausführung bestimmt. Wenn er n-mal ausgeführt wird, beträgt die Zeitkomplexität O(n).

1. Blasensortierung

Analyse: 1. Vergleichen Sie zwei benachbarte Elemente, wenn das erstere größer als das letztere ist.

2. In der ersten Runde sollte das letzte Element das größte sein.

3. Vergleichen Sie zwei benachbarte Elemente gemäß Schritt 1. Da das letzte Element zu diesem Zeitpunkt bereits das größte ist, besteht keine Notwendigkeit, das letzte Element zu vergleichen.

 

function sort(elements){
 for(var i=0;i<elements.length-1;i++){
  for(var j=0;j<elements.length-i-1;j++){
   if(elements[j]>elements[j+1]){
    var swap=elements[j];
    elements[j]=elements[j+1];
    elements[j+1]=swap;
   }
  }
 }
}
 
var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log(&#39;before: &#39; + elements);
sort(elements);
console.log(&#39; after: &#39; + elements);
Nach dem Login kopieren

2. Schnellsortierung

Analyse: Die Daten werden im ersten Sortierdurchgang in zwei Teile geteilt Teil ist kleiner als alle Daten im anderen Teil. Rufen Sie es dann rekursiv auf und führen Sie eine schnelle Sortierung auf beiden Seiten durch.

function  quickSort(elements) {
 
  if (elements.length <= 1) { return elements; }
 
    var pivotIndex = Math.floor(elements.length / 2);
 
    var pivot = elements.splice(pivotIndex, 1)[0];
 
 
  var left = [];
 
  var right = [];
 
  for (var i = 0; i < elements.length; i++){
 
    if (elements[i] < pivot) {
 
      left.push(elements[i]);
 
    } else {
 
      right.push(elements[i]);
 
    }
 
  }
 
  return quickSort(left).concat([pivot], quickSort(right));
 
};
 
var elements=[5,6,2,1,3,8,7,1.2,5.5,4.5];
alert(quickSort(elements));
Nach dem Login kopieren

3. Einfügungssortierung

Analyse:

(1) Ab dem ersten Element kann davon ausgegangen werden, dass das Element sortiert wurde

(2) Nehmen Sie das nächste Element heraus und scannen Sie es von hinten nach vorne in der sortierten Elementsequenz

(3) Wenn das Element (sortiert) größer als das neue Element ist, verschieben Sie das Element an die nächste Position

(4) Wiederholen Sie Schritt 3, bis Sie die Position gefunden haben, an der das sortierte Element kleiner oder gleich dem neuen Element ist

(5) Fügen Sie das neue Element an der nächsten Position ein

(6) Wiederholen Sie Schritt 2

insertSort: function(elements) {

    var i = 1,
    j, step, key, len = elements.length;

    for (; i < len; i++) {

        step = j = i;
        key = elements[j];

        while (--j > -1) {
            if (elements[j] > key) {
                elements[j + 1] = elements[j];
            } else {
                break;
            }
        }

        elements[j + 1] = key;
    }

    return elements;
}
Nach dem Login kopieren

2. Binäre Suche

Analyse: Die binäre Suche ist ebenfalls eine halbe Suche. Finden Sie zunächst einen Mittelwert, indem Sie ihn mit dem Mittelwert vergleichen. Der größere Wert wird platziert und der kleinere Wert wird links platziert. Suchen Sie dann den Mittelwert auf beiden Seiten und führen Sie den obigen Vorgang fort, bis Sie die Position gefunden haben.

(1) Rekursive Methode

function binarySearch(data,item,start,end){
    var end=end || data.length-1;
    var start=start || 0;
    var m=Math.floor((start+end)/2);
    if(item==data[m]){
        return m;
    }else if(item<data[m]){
        return binarySearch(data,item,start,m-1) //递归调用
    }else{
        return binarySearch(data,item,m+1,end);
    }
    return false;
}

    var arr=[34,12,5,123,2,745,32,4];

    binary(arr,5);
Nach dem Login kopieren

(2) Nicht-rekursive Methode

function binarySearch(data, item){
    var h = data.length - 1,
        l = 0;
    while(l <= h){
        var m = Math.floor((h + l) / 2);
        if(data[m] == item){
            return m;
        }
        if(item > data[m]){
            l = m + 1;
        }else{
            h = m - 1;
        }
    }
  
    return false;
}
var arr=[34,12,5,123,2,745,32,4];
binarySearch(arr,5);
Nach dem Login kopieren


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