Informationen zum Sortieralgorithmus von JS Hill (ausführliches Tutorial)

Dieser Artikel stellt hauptsächlich die Implementierungsmethoden der Hill-Sortierung und der schnellen Sortierung des JS-Sortieralgorithmus vor. Er analysiert die Prinzipien der Hill-Sortierung und der schnellen Sortierung und zeigt die JavaScript-Implementierungstechniken in Form von Beispielen an

Die Beispiele in diesem Artikel beschreiben die Implementierungsmethoden der Hill-Sortierung und der schnellen Sortierung des JS-Sortieralgorithmus. Geben Sie es wie folgt als Referenz an alle weiter:

Hügelsortierung:

Definieren Sie eine Intervallsequenz, zum Beispiel 5, 3, 1 . Bei der ersten Verarbeitung werden alle Elemente mit einem Intervall von 5 verarbeitet, beim nächsten Mal mit einem Intervall von 3 und beim letzten Mal werden Elemente mit einem Intervall von 1 verarbeitet. Das heißt, benachbarte Elemente führen eine standardmäßige Einfügungssortierung durch.

Zu Beginn der letzten Verarbeitung befinden sich die meisten Elemente an der richtigen Position und der Algorithmus muss nicht viele Elemente austauschen, was fortgeschrittener ist als das Einfügen von Elementen.

ZeitkomplexitätO(n*logn)

function shellSort(){
  var N=arr.length;
  var h=1;
  while(h<N/3){
    h=3*h+1;//设置间隔
  }
  while(h>=1){
    for(var i=h; i<N; i++){
      for(j=i; j>=h && arr[j]<arr[j-h]; j-=h){
        swap(arr, j, j-h);
      }
    }
    h=(h-1)/3;
  }
}
function swap(array, i, j){//两个数调换
  var temp =array[j];
  array[j]=array[i];
  array[i]=temp;
}

Schnellsortierung:

Rekursiv übergeben Zerlegen Sie die Daten in verschiedene Teilsequenzen mit kleineren und größeren Elementen und wiederholen Sie diesen Schritt, bis alle Daten geordnet sind.

Wählen Sie einen Benchmark-Wert und geben Sie den Wert, der kleiner als der Benchmark-Wert ist, in ein Array ein. Diejenigen, die größer als der Benchmark-Wert sind, werden in einem Array platziert.

ZeitkomplexitätO(n*logn)

function quickSort(arr){
  if(arr.length==0){
    return [];
  }
  var left=[];
  var right=[];
  var p=arr[0];
  for(var i=1; i<arr.length; i++){
    if(arr[i]<p){
      left.push(arr[i]);
    }else{
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat(p,quickSort(right));
}

Das Obige habe ich für alle zusammengestellt. Ich hoffe, dass es in Zukunft für alle hilfreich sein wird.

Verwandte Artikel:

Was Sie über Null- und Falschwerte in JavaScript sagen können

Über automatisierte Builds in Webpack (ausführliches Tutorial )

So implementieren Sie eine Reihe von Funktionen wie das Hochladen von Bildern im WeChat-Miniprogramm

So erstellen Sie ein universelles Datensimulationsframework für das Frontend (ausführliches Tutorial)

Das obige ist der detaillierte Inhalt vonInformationen zum Sortieralgorithmus von JS Hill (ausführliches Tutorial). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!