Codegrafische Analyse der JavaScript-Implementierung des Schnellsortierungsalgorithmus-js-Tutorial-php.cn

Codegrafische Analyse der JavaScript-Implementierung des Schnellsortierungsalgorithmus

黄舟

Freigeben： 2017-04-15 09:31:27

Original

1531 Leute haben es durchsucht

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>

Nach dem Login kopieren

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!