So implementieren Sie eine schnelle Sortierung mit js

Quick Sort, der in der Praxis auch am häufigsten verwendete Sortieralgorithmus, ist schnell und effizient. Wie der Name schon sagt, ist Quick Sort der beste Sortieralgorithmus.

1) Algorithmusprinzip

Die Grundidee der schnellen Sortierung: Sortieren Trennen Sie die zu sortierenden Datensätze in einem Durchgang in zwei unabhängige Teile. Die Schlüsselwörter eines Teils des Datensatzes sind kleiner als die Schlüsselwörter des anderen Teils. Anschließend können Sie die beiden Teile der Datensätze separat sortieren die gesamte Sequenz.

2) Algorithmusbeschreibung

Die Schnellsortierung verwendet die Divide-and-Conquer-Methode, um eine Zeichenfolge (Liste) in zu unterteilen zwei Unterlisten. Der spezifische Algorithmus wird wie folgt beschrieben:

f35d6e602fd7d0f0edfa6f7d103c1b57 Wählen Sie ein Element aus der Sequenz aus, das als „Pivot“ bezeichnet wird ;2> Ordnen Sie das Array neu an, sodass alle Elemente, die kleiner als der Basiswert sind, vor der Basis platziert werden und alle Elemente, die größer als der Basiswert sind, hinter der Basis platziert werden (die gleiche Zahl kann auf beiden Seiten platziert werden). Nachdem diese Partition beendet wurde, befindet sich die Basis in der Mitte der Sequenz. Dies wird als Partitionsoperation bezeichnet.

5bdf4c78156c7953567bb5a0aef2fc53

3) JavaScript-Code-Implementierung

4) Algorithmusanalyse

function paritition(arr, low, high) {
  let pivot = arr[low];
  while (low < high) {
    while (low < high && arr[high] > pivot) {
      --high;
    }
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot) {
      ++low;
    }
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}
function quickSort(arr, low, high) {
  if (low < high) {
    let pivot = paritition(arr, low, high);
    quickSort(arr, low, pivot - 1);
    quickSort(arr, pivot + 1, high);
  }
  return arr;
}
  var arr=[1,45,37,5,48,15,37,26,29,2,46,4,17,50,52];    
  console.log(quickSort(arr,0,arr.length-1));

Bester Fall: T(n) = O(nlogn)

Schlimmster Fall: T (n) = O(n^2)

Durchschnittlicher Fall: T(n) = O(nlogn)

Liste der zehn besten Algorithmen:

1.

Verwenden Sie JavaScript, um die zehn besten klassischen Sortieralgorithmen zu implementieren – Blasensortierung

2.

Verwenden Sie JavaScript, um die Top Ten der klassischen Sortieralgorithmen zu implementieren – Auswahlsortierung

3.Verwenden Sie JavaScript zur Implementierung Die zehn besten klassischen Sortieralgorithmen – Einfügungssortierung

Das obige ist der detaillierte Inhalt vonSo implementieren Sie eine schnelle Sortierung mit js. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!