Algorithmusideen zur Implementierung der schnellen Sortierung in JavaScript

Dieser Artikel stellt hauptsächlich die algorithmischen Ideen zur Implementierung einer schnellen Sortierung vor. Er hat einen gewissen Referenzwert. Jetzt können Freunde in Not darauf verweisen.

Die derzeit am häufigsten verwendete Sortierung Algorithmus ist wahrscheinlich Es gibt sieben oder acht Typen, von denen „Quicksort“ der am weitesten verbreitete und schnellere ist. Es wurde 1960 vom Turing-Preisträger Tony Hall (C. A. R. Hoare) vorgeschlagen.

Die Idee der schnellen Sortierung ist sehr einfach:

(1) Wählen Sie im Datensatz ein Element als „Pivot“. 🎜 >

(2) Alle Elemente, die kleiner als „base“ sind, werden nach links von „base“ verschoben; alle Elemente, die größer als „base“ sind, werden nach rechts von „base“ verschoben ) Für die beiden Teilmengen links und rechts der „Grundlinie“ wiederholen Sie den ersten und zweiten Schritt, bis alle Teilmengen nur noch ein Element haben.

Zum Beispiel gibt es jetzt einen Datensatz {85. 24, 63, 45, 17, 31, 96, 50}, wie sortiere ich sie?

Der erste Schritt besteht darin, das mittlere Element 45 als „Basis“ auszuwählen (der Basiswert kann sein). willkürlich. Wählen Sie, aber es ist einfacher zu verstehen, den Mittelwert zu wählen.)

Der zweite Schritt besteht darin, jedes Element mit der „Grundlinie“ zu vergleichen, um zwei Teilmengen zu bilden, nämlich eine „weniger als 45“ und die andere „größer oder gleich 45“.

Der dritte Schritt besteht darin, den ersten und zweiten Schritt für die beiden Teilmengen zu wiederholen, bis nur noch eine vorhanden ist Element in allen Teilmengen übrig.

Folgen Sie den vorherigen Schritten und definieren Sie eine QuickSort-Funktion:

var quickSort = function(arr) { //参数是一个数组
　　if (arr.length <= 1) { return arr; } //检查数组的元素个数，如果小于等于1，就返回。
　　var pivotIndex = Math.floor(arr.length / 2); //选择"基准"（pivot），并将其与原数组分离，再定义两个空数组，用来存放一左一右的两个子集。
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){ //开始遍历数组，小于"基准"的元素放入左边的子集，大于基准的元素放入右边的子集。
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat([pivot], quickSort(right));
};

Um die obige Animation zu implementieren:

Algorithmusidee:

Wählen Sie ein Element aus der Sequenz aus, das als „Pivot“ bezeichnet wird >

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, nach der Basis platziert werden (auf beiden Seiten kann die gleiche Zahl stehen). Beim Verlassen der Partition befindet sich die mittlere Position im Array. Dies wird als Partitionsoperation bezeichnet. Das Unterarray wird mit Elementen, die kleiner als der Basiswert sind, und dem Unterarray mit Elementen, die größer sind, rekursiv sortiert als der Basiswert;
Implementierungscode:

2. function quickSort(arr, left, right) { 
   　　var len = arr.length,
   　　partitionIndex,
   　　left = typeof left != 'number' ? 0 : left,
   　　right = typeof right != 'number' ? len - 1 : right;
    
    
   　　if (left < right) {
   　　partitionIndex = partition(arr, left, right);
   　　quickSort(arr, left, partitionIndex-1);
   　　quickSort(arr, partitionIndex+1, right);
   　　}
   　　return arr;
   }
   function partition(arr, left ,right) { // 分区操作
   　　var pivot = left,                // 设定基准值（pivot）
   　　　　index = pivot + 1;
   　　for (var i = index; i <= right; i++) {
   　　　　if (arr[i] < arr[pivot]) {
   　　　　　　swap(arr, i, index);
   　　　　　　index++;
   　　　　}
   　　}
   　　swap(arr, pivot, index - 1);
   　　 return index-1;
   }
    
   function swap(arr, i, j) {
   　　var temp = arr[i];
   　　arr[i] = arr[j];
   　　arr[j] = temp;
   }
   function partition2(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 quickSort2(arr, low, high) {
   　　if (low < high) {
   　　let pivot = partition2(arr, low, high);
   　　quickSort2(arr, low, pivot - 1);
   　　quickSort2(arr, pivot + 1, high);
   　　}
   　　return arr;
   }

   Ich hoffe, dass es für alle hilfreich ist Inhalt, achten Sie bitte auf die chinesische PHP-Website

Das obige ist der detaillierte Inhalt vonAlgorithmusideen zur Implementierung der schnellen Sortierung in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!