So implementieren Sie die JS Hill-Sortierung und die schnelle Sortierung

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. Ich hoffe, es kann allen helfen.

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:

Zerlegen Sie die Daten rekursiv in verschiedene Teilsequenzen mit kleineren und größeren Elementen. Wiederholen Sie diesen Schritt, bis alle Daten in Ordnung 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));
}

Schnellsortierung eignet sich für große Datensammlungen. Bei der Verarbeitung kleiner Datensätze nimmt die Leistung jedoch ab.

Verwandte Empfehlungen:

Detaillierte Analyse der Methode zur Implementierung des Hill-Sortieralgorithmus in PHP

Hill-Sortierung der JavaScript-Sortierung Algorithmus 2 Beispiele_Grundkenntnisse

JavaScript Hill-Sortierung, schnelle Sortierung, Zusammenführungssortierung-Algorithmus_Javascript-Kenntnisse

Das obige ist der detaillierte Inhalt vonSo implementieren Sie die JS Hill-Sortierung und die schnelle Sortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!