suchen

Heim  >  Artikel  >  Web-Frontend  >  Beispielanalyse der JavaScript-Implementierung des Auswahlsortierungsalgorithmus (Bild)

Beispielanalyse der JavaScript-Implementierung des Auswahlsortierungsalgorithmus (Bild)

黄舟
黄舟Original
2017-04-15 09:31:361861Durchsuche

Dieser Artikel stellt hauptsächlich den von JavaScript implementierten Auswahlsortierungsalgorithmus vor. Er analysiert das Prinzip, die Implementierungsschritte und die damit verbundenen Bedienungsfähigkeiten der Auswahlsortierung in Form von Beispielen kann darauf verweisen.

Das Beispiel in diesem Artikel beschreibt den in JavaScript implementierten Auswahlsortierungsalgorithmus. Teilen Sie es als Referenz mit allen:

Einfache Auswahlsortierung ist die bekannteste Vergleichsmethode. Die Algorithmusidee lautet: von Beginnend am Anfang des Arrays , vergleichen Sie das erste Element mit den anderen Elementen. Nachdem alle Elemente überprüft wurden, wird das kleinste Element an der ersten Position des Arrays platziert und der Algorithmus fährt ab der zweiten Position fort. Dieser Vorgang wird fortgesetzt, bis die vorletzte Position des Arrays erreicht ist und alle Daten sortiert werden.

Der Code lautet wie folgt: 

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>JavaScript选择排序</title>
</head>
<body>
<script type="text/javascript">
 function selectSort(nums){//选择排序
  var min;//最小值
  for(var outer=0;outer<nums.length-1;outer++){//外循环选中元素
   min=outer;
   for(var inner=outer+1;inner<=nums.length;++inner){
    if(nums[inner]<nums[min]){//如果内循环中元素比选中元素小
     min=inner;//将其标为最小元素
    }//直到每次外循环的最小元素
    swap(nums,outer,min);//最小值被调整到合适的位置
   }
  }
 }
 function swap(arr,i,j){//交换位置
  var temp=arr[i];
  arr[i]=arr[j];
  arr[j]=temp;
 }
 function show(nums){//显示数组
  for(var i=0;i<nums.length;i++){
   document.write(nums[i]+&#39; &#39;);
  }
  document.write(&#39;<br>&#39;);
 }
 var nums=[6,8,0,6,7,4,3,5,5,10];
 show(nums);//6 8 0 6 7 4 3 5 5 10
 selectSort(nums);
 show(nums);//0 3 4 5 5 6 6 7 9 10
</script>
</body>
</html>

Die Analyse zeigt, dass die zeitliche Komplexität der einfachen Auswahlsortierung O(n2) beträgt. Der Hauptvorgang der Auswahlsortierung ist der Vergleich zwischen Schlüsselwörtern. Daher sollte die Verbesserung der einfachen Auswahlsortierung damit beginnen, Vergleiche zu reduzieren. Tatsächlich gibt es im wirklichen Leben ein gutes Beispiel, nämlich die Gesamtmeisterschaft des Spiels. Um den Champion unter 8 Personen auszuwählen, sind nicht unbedingt 7+6+5=18 Spiele erforderlich. Dies kann durch einen paarweisen Vergleich erfolgen, der 11 Spiele umfasst. Diese Methode heißt Tree Selection Sort.

Baumauswahlsortierung ist eine Auswahlsortiermethode, die auf der Idee eines Turniers basiert. Vergleichen Sie zunächst die Schlüsselwörter von n Datensätzen paarweise und dann n/2 davon Die kleineren werden dann paarweise verglichen, bis das kleinste Schlüsselwort gefunden ist. Es kann durch einen vollständigen Binärbaum dargestellt werden, da die Tiefe eines vollständigen Binärbaums mit n Knoten log2n + 1 beträgt. Für jede Auswahl eines Sub-Small-Schlüsselworts sind während des Sortiervorgangs nur log2n-Operationen erforderlich, sodass seine zeitliche Komplexität O (nlog2n) , aber diese Sortierung hat den Nachteil, dass sie viel Platz beansprucht.

Also müssen wir eine bessere Sortierung einführen, nämlich die

Heap-Sortierung.

Anhang: Heap-Sortieralgorithmus

Heap-Sortierung erfordert nur einen zusätzlichen Speicherplatz für die Datensatzgröße , belegt jeder zu sortierende Datensatz nur einen Speicherplatz.

Heap-Sortierung nutzt die Funktion, dass der oben im großen Root-Heap (oder kleinen Root-Heap) aufgezeichnete Schlüssel der größte (oder kleinste) ist, sodass der Datensatz mit dem größten (oder kleinsten) Das im aktuellen ungeordneten Bereich ausgewählte Schlüsselwort wird zu Gotta be simple. Nehmen wir als Beispiel den großen Heap. Die grundlegenden Vorgänge beim Sortieren sind wie folgt:

Der erste Schritt besteht darin, den Heap zu erstellen. Beginnend bei len2 und weiter bis zu den ersten Knoten, wobei len die Anzahl der Elemente im Heap ist. Der Prozess zum Erstellen eines Heaps ist ein linearer Prozess. Der Prozess zum Anpassen des Heaps wird immer von len2 auf 0 aufgerufen. Die Zeitkomplexität beim Erstellen eines Heaps beträgt O(n).

Als nächstes folgt der Anpassungsheap Der Anpassungsheap wird beim Heap-Aufbau und der Heap-Sortierung verwendet. Die Idee besteht darin, den Knoten i und seinen untergeordneten Knoten
links( i) zu vergleichen ) und rechts(i), wählen Sie den größten (oder kleinsten) der drei aus. Wenn der größte (kleinste) Wert nicht Knoten i, sondern einer seiner untergeordneten Knoten ist, tauschen Sie die beiden Knoten aus und fahren Sie fort Rekursion. Dann Heap-Sortierung:
Nehmen Sie den Wurzelknoten des Heaps heraus, ersetzen Sie den Wurzelknoten durch das letzte Element, setzen Sie den Heap-Anpassungsprozess mit den ersten Len-1-Knoten fort, und sprechen Sie dann über das Entfernen des Wurzelknotens, bis alle Knoten entfernt sind. Die zeitliche Komplexität der Heap-Anpassung beträgt O(log2n)Die zeitliche Komplexität der Heap-Sortierung beträgt also O(nlog2n). Die Heap-Sortierung ist eine In-Place-Sortierung und ihr Hilfsraum ist O(1). Aber es ist instabil (Die Stabilität der Sortierung bedeutet, dass sich ihre relativen Positionen vor und nach der Sortierung nicht ändern, wenn die sortierte Reihenfolge zwei identische Elemente enthält).
Das Folgende simuliert den Prozess des Aufbaus eines Heaps:

Heap-Sortierung lohnt sich nicht für Dateien mit einer kleinen Anzahl von Datensätzen, ist es aber dennoch geeignet für Feilen mit großem n Ziemlich effektiv.

Das obige ist der detaillierte Inhalt vonBeispielanalyse der JavaScript-Implementierung des Auswahlsortierungsalgorithmus (Bild). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme：
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
Vorheriger Artikel：Den „+“-Operator in Javascript verstehenNächster Artikel：Den „+“-Operator in Javascript verstehen

In Verbindung stehende Artikel

Mehr sehen