Abrufalgorithmus der Javascript-Datenstruktur und algorithm_javascript-Fähigkeiten

Es gibt zwei Möglichkeiten, Daten zu finden: sequentielle Suche und binäre Suche. Die sequentielle Suche funktioniert bei Listen mit zufällig angeordneten Elementen. Die binäre Suche funktioniert mit einer sortierten Liste von Elementen. Die binäre Suche ist effizienter, es muss sich jedoch um eine sortierte Menge von Listenelementen handeln.

1: Sequentielle Suche
Bei der sequentiellen Suche werden die Listenelemente nacheinander beurteilt, beginnend mit dem ersten Element der Liste, bis das gewünschte Ergebnis gefunden wird oder das gewünschte Element erst am Ende der Liste gefunden wird.

Der Code lautet wie folgt:

function seqSearch(data,arr) {
  for(var i = 0; i < arr.length; ++i) {
    if(arr[i] == data) {
      return true;
    }
  }
  return false;
}

Wir können auch die sequentielle Suchfunktion zurückgeben, die der Position des Elements entspricht. Der Code lautet wie folgt:

function seqSearch(data,arr) {
  for(var i = 0; i < arr.length; ++i) {
    if(arr[i] == data) {
      return i;
    }
  }
  return -1;
}

Zweitens: Finden Sie die Minimal- und Maximalwerte

Der Algorithmus zum Ermitteln des Mindestwerts in einem Array lautet wie folgt:

1. Weisen Sie das erste Element des Arrays einer Variablen zu und verwenden Sie diese Variable als Minimalwert.
2. Beginnen Sie mit dem Durchlaufen des Arrays, beginnend beim zweiten Element und vergleichen Sie es mit dem aktuellen Minimalwert.
3. Wenn der Wert des aktuellen Elements kleiner als der aktuelle Mindestwert ist, setzen Sie das aktuelle Element auf den neuen Mindestwert.
4. Gehen Sie zum nächsten Element und wiederholen Sie Schritt 3.
5. Wenn das Programm endet, wird in dieser Variablen der Mindestwert gespeichert.

Der Code lautet wie folgt:

function findMin(arr) {
  var min = arr[0];
  for(var i = 1; i < arr.length; ++i) {
    if(arr[i] < min) {
      min = arr[i];
    }
  }
  return min;
}

Der Algorithmus zum Ermitteln des Maximalwerts ähnelt dem oben genannten Minimalwert. Stellen Sie zunächst das erste Element im Array auf den Maximalwert ein und vergleichen Sie dann jedes verbleibende Element des Arrays mit dem aktuellen Maximalwert Der Wert des aktuellen Elements ist größer als der aktuelle Maximalwert. Weisen Sie dann den Wert des Elements dem Maximalwert zu. Der Code lautet wie folgt:

function findMax(arr) {
  var max = arr[0];
  for(var i = 1; i < arr.length; ++i) {
    if(arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
 }

Drei: Binäre Suchmethode.

Wenn die gesuchten Daten geordnet sind, ist der binäre Suchalgorithmus effizienter als der sequentielle Suchalgorithmus. Das Grundprinzip des binären Suchalgorithmus lautet wie folgt:

1. Setzen Sie die erste Position des Arrays auf die untere Grenze (0).
2. Setzen Sie die Position des letzten Elements des Arrays auf die obere Grenze (die Länge des Arrays minus 1).
3. Wenn die untere Grenze gleich oder kleiner als die obere Grenze ist, gehen Sie wie folgt vor:
A. Stellen Sie den Mittelpunkt auf (obere Grenze plus untere Grenze) geteilt durch 2.
B. Wenn das Element am Mittelpunkt kleiner als der Abfragewert ist, legen Sie die untere Grenze auf den Index des Mittelpunktelements plus 1 fest.
C. Wenn das Element am Mittelpunkt größer als der Abfragewert ist, legen Sie die obere Grenze auf den Index des Mittelpunktelements minus 1 fest.
D. Andernfalls handelt es sich bei dem Mittelpunktelement um die zu findenden Daten, die zurückgegeben werden können.

Der Code lautet wie folgt:

// 二分查找算法
function binSearch(data,arr) {
var lowerBound = 0;
  var upperBound = arr.length - 1;
  while(lowerBound <= upperBound) {
    var mid = Math.floor((upperBound + lowerBound)/2);
    if(arr[mid] < data) {
      lowerBound = mid + 1;
    }else if(arr[mid] > data) {
      upperBound = mid - 1;
    }else {
      return mid;
    }
  }
  return -1;
}
 // 快速排序
function qSort(list) {
  if(list.length == 0) {
    return [];
  }
  // 存储小于基准值的值
  var left = [];
  // 存储大于基准值的值
  var right = [];
  var pivot = list[0];
  for(var i = 1; i < list.length; i++) {
    if(list[i] < pivot) {
      left.push(list[i]);
    }else {
      right.push(list[i])
    }
  }
  return qSort(left).concat(pivot,qSort(right));
}
 // 测试代码
var numbers = [0,9,1,8,7,6,2,3,5,4];
var list = qSort(numbers);
console.log(binSearch(6,list));

4: Berechnen Sie die Anzahl der Wiederholungen;
Wenn die Funktion binSearch() des binären Suchalgorithmus einen bestimmten Wert findet und andere gleiche Werte im Datensatz vorhanden sind, wird die Funktion in der Nähe ähnlicher Werte positioniert Die linke oder rechte Seite des gefundenen Werts wird angezeigt.

Dann besteht unsere einfachste Lösung darin, zwei Schleifen zu schreiben, eine, die den Datensatz gleichzeitig nach unten oder nach links durchläuft und dabei die Anzahl der Wiederholungen zählt, und die dann nach oben oder nach rechts verläuft und dabei die Anzahl der Wiederholungen zählt. Der Code lautet wie folgt:

// 计算重复次数
function count(data,arr) {
  var count = 0;
  var arrs = [];
  var position = binSearch(data,arr);
  if(position > -1) {
    ++count;
    arrs.push({"index":count});
    for(var i = position -1; i > 0; --i) {
      if(arr[i] == data) {
        ++count;
        arrs.push({"index":count});
      }else {
        break;
      }
    }
    for(var i = position + 1; i < arr.length; ++i) {
      if(arr[i] == data) {
        ++count;
        arrs.push({"index":count});
      }else {
        break;
      }
    }
  }
  return arrs;
}
 // 测试重复次数的代码
var arr = [0,1,1,1,2,3,4,5,6,7,8,9];
var arrs = count(1,arr);
console.log(arrs);
console.log(arrs.length);

Wie unten gezeigt: