Heim >Web-Frontend >js-Tutorial >Codegrafische Analyse der JavaScript-Implementierung des Schnellsortierungsalgorithmus

Codegrafische Analyse der JavaScript-Implementierung des Schnellsortierungsalgorithmus

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

Dieser Artikel stellt hauptsächlich den auf JavaScript basierenden Schnellsortierungsalgorithmus vor. Er analysiert das Prinzip der Schnellsortierung und stellt die Operationsschritte und zugehörigen Implementierungstechniken der Javascript-Schnellsortierung in Form von Beispielen bereit it Sie können sich auf Folgendes beziehen:

Das Beispiel in diesem Artikel beschreibt den auf JavaScript basierenden Schnellsortierungsalgorithmus. Teilen Sie es als Referenz mit allen. Die Einzelheiten lauten wie folgt:

Lassen Sie mich zunächst die Blasensortierung vorstellen. Der Prozess der Blasensortierung ist sehr einfach . Zuerst wird der Schlüssel eines Datensatzes mit dem Schlüssel des zweiten Datensatzes verglichen. Wenn die Reihenfolge umgekehrt ist, werden die beiden Schlüssel ausgetauscht und dann der zweite und dritte verglichen, bis der letzte Vergleich abgeschlossen ist. Dies ist das erste Bubbling, und als Ergebnis wird der Datensatz mit dem größten Schlüsselwort an der letzten Position platziert. Blasen Sie dann die ersten n-1 Elemente der Sequenz ein zweites Mal auf und wählen Sie das vorletzte aus. Und so weiter, bis alle ausgewählt sind und das Sprudeln endet .

Durch die Analyse kann der Schluss gezogen werden, dass die zeitliche Komplexität der Blasensortierung O(n2) beträgt.

Schnellsortierung ist eine Verbesserung gegenüber der Blasensortierung. Sie ist eine der schnellsten Sortierungen zur Verarbeitung großer Datenmengen, über die Rekursionsmethode Zerlegen Sie die Daten nacheinander in verschiedene Teilsequenzen mit kleineren und größeren Elementen und wiederholen Sie den Vorgang, bis alle Daten geordnet sind. Dieser Algorithmus muss zunächst einen Basiswert auswählen und um den Basiswert herum vorgehen.

Ein Beispiel lautet wie folgt:

Die Algorithmusidee lautet wie folgt:

Auswählen ein Basiselement und fügen Sie die Liste hinzu. Teilen Sie die Liste in zwei Teilsequenzen; platzieren Sie alle Elemente, die kleiner als das Referenzelement sind, vorne und größere hinten 🎜>

Wiederholen Sie die beiden oben genannten Schritte für die Unterfolge kleinerer Elemente und die Unterfolge größerer Elemente.

Wir implementieren den Code über

wie folgt:

In Bezug auf die durchschnittliche Zeit schnelle Sortierung gilt derzeit als die beste interne Sortiermethode. Die schnelle Sortierung eignet sich sehr gut für große Datensätze, bei der Verarbeitung kleiner Datensätze nimmt jedoch die Leistung ab. Seine zeitliche Komplexität beträgt

O(nlog2n)

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>JavaScript快速排序</title>
</head>
<body>
<script type="text/javascript">
  function qSort(nums) {//快速排序
    if(nums.length==0){
      return [];
    }
    var lesser=[];
    var greater=[];
    var pivot=nums[0];//选择基准元素
    for(var i=1;i<nums.length;i++){
      if(nums[i]<pivot){//分成两个之序列
        lesser.push(nums[i]);
      }else{
        greater.push(nums[i]);
      }
    }
    return qSort(lesser).concat(pivot,qSort(greater));//递归
  }
  function show(nums){//显示数组
    for(var i=0;i<nums.length;i++){
      document.write(nums[i]+&#39; &#39;);
    }
    document.write(&#39;<br>&#39;);
  }
  var nums=[68,80,12,80,95,70,79,27,88,93];
  show(nums);//newNums
  var newNums=qSort(nums);//希尔排序
  show(newNums);//0 0 2 3 4 5 5 6 8 9
</script>
</body>
</html>

Das obige ist der detaillierte Inhalt vonCodegrafische Analyse der JavaScript-Implementierung des Schnellsortierungsalgorithmus. 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：Beispielanalyse der JavaScript-Implementierung des Auswahlsortierungsalgorithmus (Bild)Nächster Artikel：Beispielanalyse der JavaScript-Implementierung des Auswahlsortierungsalgorithmus (Bild)

In Verbindung stehende Artikel

Mehr sehen