js grundlegender Algorithmus: Blasensortierung, binäre Suche-js-Tutorial-php.cn

js grundlegender Algorithmus: Blasensortierung, binäre Suche

高洛峰

Freigeben： 2016-10-08 17:51:06

Original

1380 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