Dieses Mal zeige ich Ihnen, wie Sie die JS-Array-Sortiermethode verwenden Vorsichtsmaßnahmen Das Folgende ist ein praktischer Fall, schauen wir uns das an.
In der Algorithmenklasse werden wir mit vielen Arten von Sortieralgorithmen konfrontiert, wie z. B. Blasensortierung, Auswahlsortierung, Schnellsortierung, Heapsortierung usw. Welchen Sortieralgorithmus verwendet die Sortiermethode von Javascript? Um das herauszufinden, schauen Sie sich einfach den Quellcode der Version 8 an. Die Implementierung von Array.sort in Version 8 erfolgt mithilfe von JavaScript. Auf den ersten Blick wird der Schnellsortierungsalgorithmus verwendet, der jedoch offensichtlich komplizierter ist als die uns bekannte Schnellsortierung. Was genau ist also die Komplexität? Warum es so kompliziert machen? Dieser Frage gehen wir heute nach.
Schnellsortierungsalgorithmus
Der Schnellsortierungsalgorithmus wird als Schnellsortierungsalgorithmus bezeichnet, da er eine optimale und durchschnittliche Zeitkomplexität von O(nlogn) erreichen kann, was sehr weit verbreitet ist Verwendeter Sortieralgorithmus. Das Prinzip ist nicht kompliziert. Suchen Sie zuerst ein Benchmark-Element (Pivot, jedes Element ist akzeptabel) und vergleichen Sie dann alle Elemente mit dem Pivot-Element. Wenn sie kleiner als das Pivot-Element sind, fügen Sie sie in einen Satz ein Führen Sie dann eine schnelle Sortierung für diese beiden Sätze durch und erhalten Sie schließlich eine vollständig sortierte Sequenz.
Der Kern der schnellen Sortierung besteht also darin, das ursprüngliche Array kontinuierlich in kleine Arrays zu zerlegen und dann die gleiche Verarbeitung für die kleinen Arrays durchzuführen. Dies ist eine typische Entwurfsidee für einen Divide-and-Conquer-Algorithmus. Die Implementierung eines einfachen Quicksort-Algorithmus ist nicht schwierig. Versuchen wir es:
function QuickSort(arr, func) {
if (!arr || !arr.length) return [];
if (arr.length === 1) return arr;
var pivot = arr[0];
var smallSet = [];
var bigSet = [];
for (var i = 1; i < arr.length; i++) {
if (func(arr[i], pivot) < 0) {
smallSet.push(arr[i]);
} else {
bigSet.push(arr[i]);
}
}
return QuickSort(smallSet, func).concat([pivot]).concat(QuickSort(bigSet, func));
}Dies ist eine sehr einfache Implementierung, bei der das erste Element des Arrays als Basiselement ausgewählt wird.
In-Place-Sortierung
Wir können feststellen, dass wir im obigen Algorithmus tatsächlich ein neues Array als Berechnungsergebnis erstellen. Dies ist aus Platzgründen unwirtschaftlich Perspektive. Der JavaScript-Schnellsortierungsalgorithmus erstellt kein neues Array wie der obige Code, sondern sortiert die Elemente, indem er die Positionen der Elemente basierend auf dem ursprünglichen Array austauscht. Daher ändert die Sortiermethode ähnlich wie die Push-, Pop- und Splice-Methoden auch das ursprüngliche Array Objekt !
Wir haben zuvor gesagt, dass der Kern der schnellen Sortierung darin besteht, das Array zu zerschneiden. Wenn Sie also nur Elemente im ursprünglichen Array austauschen, wie schneidet man das Array ab? Es ist ganz einfach, wir müssen das Array nicht wirklich zerschneiden, wir müssen uns nur die Anfangs- und Endindexnummern jedes Teils merken. Angenommen, es gibt ein Array [12, 4, 9, 2, 18, 25] und das erste Element 12 wird als Basiselement ausgewählt. Dann wird das Array gemäß dem ursprünglichen Schnellsortierungsalgorithmus in zwei Teile geteilt kleine Arrays: [4, 9, 2], 12, [18, 25]. Aber wir können es auch nicht schneiden, indem wir zuerst das ursprüngliche Array durch Vergleichen und Austauschen von Elementen in [4, 9, 2, 12, 18, 25] ändern und dann basierend auf der Position des Referenzelements 12 denken, dass die Elemente 0 bis 2 sind eine Gruppe, die Elemente Nr. 4 bis 5 sind eine Gruppe. Der Einfachheit halber nenne ich hier die Partition, die aus Elementen besteht, die kleiner als das Referenzelement sind, die Dezimalpartition, und die andere Partition wird als große Zahlenpartition bezeichnet . Dies ist der Partitionierung einer Computerfestplatte sehr ähnlich. Dabei wird die Festplatte nicht wirklich in Laufwerk C und D unterteilt, sondern einige Start- und Endpositionen erfasst und logisch in mehrere Partitionen unterteilt. In ähnlicher Weise nennen wir diesen Prozess im Schnellsortierungsalgorithmus auch Partition. Daher muss ich meine vorherige Aussage ändern. Der Kern des Schnellsortierungsalgorithmus ist die Partitionierung.
Nachdem wir so viel gesagt haben, implementieren wir eine schnelle Sortierung mit Partitionen:
function swap(arr, from, to) {
if (from == to) return;
var temp = arr[from];
arr[from] = arr[to];
arr[to] = temp;
}
function QuickSortWithPartition(arr, func, from, to) {
if (!arr || !arr.length) return [];
if (arr.length === 1) return arr;
from = from || 0;
to = to || arr.length - 1;
var pivot = arr[from];
var smallIndex = from;
var bigIndex = from + 1;
for (; bigIndex <= to; bigIndex++) {
if (func(arr[bigIndex], pivot) < 0) {
smallIndex++;
swap(arr, smallIndex, bigIndex);
}
}
swap(arr, smallIndex, from);
QuickSortWithPartition(arr, func, from, smallIndex - 1);
QuickSortWithPartition(arr, func, smallIndex + 1, to);
return arr;
}Es scheint, dass der Code viel länger ist, aber er ist nicht zu kompliziert. Da es sich dabei um den Austausch von Array-Elementen handelt, implementieren wir zunächst eine Swap-Methode, um den Elementaustausch abzuwickeln. Im Schnellsortierungsalgorithmus werden zwei Parameter hinzugefügt, von und bis, die jeweils angeben, von welchem Teil des Arrays der Startindex und bis der Endindex ist das gesamte Array.
同样的，我用最简单的方式选取基准元素，即所要处理分区的第一个元素。然后我定义了smallIndex和bigIndex两个变量，分别表示的是左侧小数分区的终止索引和右侧大数分区的终止索引。什么意思？就是说从第一个元素（基准元素）到第smallIndex个元素间的所有元素都比基准元素小，从第smallIndex + 1到第bigIndex个元素都比基准元素大。一开始没有比较时，很显然这两部分分区都是空的，而比较的过程很简单，直接是bigIndex向右移，一直移到分区尾部。每当bigIndex增加1，我们会进行一次判断，看看这个位置上的元素是不是比基准元素大，如果大的话，不用做处理，它已经处于大数分区了；但如果比基准元素小，就需要进行一次交换。怎么交换呢？首先将smallIndex增加1，意味着小数分区增加了一个元素，但此时smallIndex位置的元素很明显是一个大数（这个说法其实不对，如果之前大数分区里面没有元素，此时smallIndex和bigIndex相等，但对交换没有影响），而在bigIndex位置的元素是一个小数，所以只要把这两个位置的元素交换一下就好了。
最后可别忘了一开始的起始元素，它的位置并不正确，不过只要将它和smallIndex位置的元素交换位置就可以了。同时我们得到了对应的小数分区[from...smallIndex - 1]和大数分区[smallIndex + 1...to]。再对这两个分区递归排序即可。
分区过程的优化
上面的分区过程（仅仅）还是有一定的优化空间的，因为上面的分区过程中，大数分区和小数分区都是从左向右增长，其实我们可以考虑从两侧向中间遍历，这样能有效地减少交换元素的次数。举个例子，例如我们有一个数组[2, 1, 3, 1, 3, 1, 3]，采用上面的分区算法，一共碰到三次比基准元素小的情况，所以会发生三次交换；而如果我们换个思路，把从右往左找到小于基准和元素，和从左往右找到大于基准的元素交换，这个数组只需要交换一次就可以了，即把第一个3和最后一个1交换。
我们也来尝试写一下实现：
function QuickSortWithPartitionOp(arr, func, from, to) {
if (!arr || !arr.length) return [];
from = from || 0;
to = to || arr.length - 1;
if (from >= to - 1) return arr;
var pivot = arr[from];
var smallEnd = from + 1;
var bigBegin = to;
while (smallEnd < bigBegin) {
while (func(arr[bigBegin], pivot) > 0 && smallEnd < bigBegin) {
bigBegin--;
}
while (func(arr[smallEnd], pivot) < 0 && smallEnd < bigBegin) {
smallEnd++;
}
if (smallEnd < bigBegin) {
swap(arr, smallEnd, bigBegin);
}
}
swap(arr, smallEnd, from);
QuickSortWithPartitionOp(arr, func, from, smallEnd - 1);
QuickSortWithPartitionOp(arr, func, smallEnd + 1, to);
return arr;
}分区与性能
前面我们说过，快速排序算法平均时间复杂度是O(nlogn)，但它的最差情况下时间复杂度会衰弱到O(n2)。而性能好坏的关键就在于分区是否合理。如果每次都能平均分成相等的两个分区，那么只需要logn层迭代；而如果每次分区都不合理，总有一个分区是空的，那么需要n层迭代，这是性能最差的场景。
那么性能最差的场景会出现吗？对于一个内容随机的数组而言，不太可能出现最差情况。但我们平时在编程时，处理的数组往往并不是内容随机的，而是很可能预先有一定顺序。设想一下，如果一个数组已经排好序了，由于之前的算法中，我们都是采用第一个元素作为基准元素，那么必然会出现每次分区都会有一个分区为空。这种情况当然需要避免。
一种很容易的解决方法是不要选取固定位置的元素作为基准元素，而是随机从数组里挑出一个元素作为基准元素。这个方法很有效，极大概率地避免了最差情况。这种处理思想很简单，我就不另外写代码了。
然而极大概率地避免最差情况并不等于避免最差情况，特别是对于数组很大的时候，更要求我们在选取基准元素的时候要更谨慎些。
三数取中（median-of-three）
基准元素应当精心挑选，而挑选基准元素的一种方法为三数取中，即挑选基准元素时，先把第一个元素、最后一个元素和中间一个元素挑出来，这三个元素中大小在中间的那个元素就被认为是基准元素。
简单实现一下获取基准元素的方法：
function getPivot(arr, func, from, to) {
var middle = (from + to) >> 1;
var i0 = arr[from];
var i1 = arr[to];
var i2 = arr[middle];
var temp;
if (func(i0, i1) > 0) {
temp = i0;
i0 = i1;
i1 = temp;
}
if (func(i0, i2) > 0) {
arr[middle] = i0;
arr[from] = i2;
arr[to] = i1;
return i0;
} else {
arr[from] = i0;
if (func(i1, i2) > 0) {
arr[middle] = i1;
arr[to] = i2;
return i1;
} else {
arr[middle] = i2;
arr[to] = i1;
return i2;
}
}
}这个例子里我完全没管基准元素的位置，一是降低复杂度，另一个原因是下面讨论重复元素处理时，基准元素的位置没什么意义。不过我把最小的值赋给了第一个元素，最大的值赋给了第二个元素，后面处理重复元素时会有帮助。
当然，仅仅是三数取中获得的基准元素，也不见得是可靠的。于是有一些其他的取中值的方法出现。有几种比较典型的手段，一种是平均间隔取一个元素，多个元素取中位数（即多取几个，增加可靠性）；一种是对三数取中进行递归运算，先把大数组平均分成三块，对每一块进行三数取中，会得到三个中值，再对这三个中值取中位数。
不过查阅v8的源代码，发现v8的基准元素选取更为复杂。如果数组长度不超过1000，则进行基本的三数取中；如果数组长度超过1000，那么v8的处理是除去首尾的元素，对剩下的元素每隔200左右（200~215，并不固定）挑出一个元素。对这些元素排序，找出中间的那个，并用这个元素跟原数组首尾两个元素一起进行三数取中。这段代码我就不写了。
针对重复元素的处理
到目前为止，我们在处理元素比较的时候比较随意，并没有太多地考虑元素相等的问题。但实际上我们做了这么多性能优化，对于重复元素引起的性能问题并没有涉及到。重复元素会带来什么问题呢？设想一下，一个数组里如果所有元素都相等，基准元素不管怎么选都是一样的。那么在分区的时候，必然出现除基准元素外的其他元素都被分到一起去了，进入最差性能的case。
那么对于重复元素应该怎么处理呢？从性能的角度，如果发现一个元素与基准元素相同，那么它应该被记录下来，避免后续再进行不必要的比较。所以还是得改分区的代码。
function QuickSortWithPartitionDump(arr, func, from, to) {
if (!arr || !arr.length) return [];
from = from || 0;
to = to || arr.length - 1;
if (from >= to - 1) return arr;
var pivot = getPivot(arr, func, from, to);
var smallEnd = from;
var bigBegin = to;
for (var i = smallEnd + 1; i < bigBegin; i++) {
var order = func(arr[i], pivot);
if (order < 0) {
smallEnd++;
swap(arr, i, smallEnd);
} else if (order > 0) {
while (bigBegin > i && order > 0) {
bigBegin--;
order = func(arr[bigBegin], pivot);
}
if (bigBegin == i) break;
swap(arr, i, bigBegin);
if (order < 0) {
swap(arr, i, smallEnd);
smallEnd++;
}
}
}
QuickSortWithPartitionDump(arr, func, from, smallEnd);
QuickSortWithPartitionDump(arr, func, bigBegin, to);
return arr;
}简单解释一下这段代码，上文已经说过，在getPivot方法中，我将比基准小的元素放到第一位，把比基准大的元素放到最后一位。定义三个变量smallEnd、bigBegin、i，从from到smallEnd之间的元素都比基准元素小，从smallEnd到i之间的元素都和基准元素一样大，从i到bigBegin之间的元素都是还没有比较的，从bigBegin到to之间的元素都比基准元素大。了解这个关系就好理解这段代码了。遍历从smallEnd + 1到bigBegin之间的元素：
* 如果这个元素小于基准，那么smallEnd增加1，这时smallEnd位置的元素是等于基准元素的（或者此时smallEnd与i相等），交换smallEnd与i处的元素就可以了。
* 如果这个元素大于基准，相对比较复杂一点。此时让bigBegin减小1，检查大数分区前面一个元素是不是大于基准，如果大于基准，重复此步骤，不断让bigBegin减小1，直到找到不比基准大的元素（如果这个过程中，发现bigBegin与i相等，则中止遍历，说明分区结束）。找到这个不比基准大小元素时需要区分是不是比基准小。如果比基准小，需要做两步交换，先将i位置的大数和bigBegin位置的小数交换，这时跟第一种case同时，smallEnd增加1，并且将i位置的小数和smallEnd位置的元素交换。如果和基准相等，则只需要将i位置的大数和bigBegin位置的小数交换。
* 如果这个元素与基准相等，什么也不用做。
小数组优化
对于小数组（小于16项或10项。v8认为10项以下的是小数组。），可能使用快速排序的速度还不如平均复杂度更高的选择排序。所以对于小数组，可以使用选择排序法要提高性能，减少递归深度。
function insertionSort(a, func, from, to) {
for (var i = from + 1; i < to; i++) {
var element = a[i];
for (var j = i - 1; j >= from; j--) {
var tmp = a[j];
if (func(tmp, element) > 0) {
a[j + 1] = tmp;
} else {
break;
}
}
a[j + 1] = element;
}
}v8引擎没有做的优化
由于快速排序的不稳定性（少数情况下性能差，前文已经详细描述过），David Musser于1997设计了内省排序法（Introsort）。这个算法在快速排序的基础上，监控递归的深度。一旦长度为n的数组经过了logn层递归（快速排序算法最佳情况下的递归层数）还没有结束的话，就认为这次快速排序的效率可能不理想，转而将剩余部分换用其他排序算法，通常使用堆排序算法（Heapsort，最差时间复杂度和最优时间复杂度均为nlogn）。
v8引擎额外做的优化
快速排序递归很深，如果递归太深的话，很可以出现“爆栈”，我们应该尽可能避免这种情况。上面提到的对小数组采用选择排序算法，以及采用内省排序算法都可以减少递归深度。不过v8引擎中，做了一些不太常见的优化，每次我们分区后，v8引擎会选择元素少的分区进行递归，而将元素多的分区直接通过循环处理，无疑这样的处理大大减小了递归深度。我大致把v8这种处理的过程写一下：
function quickSort(arr, from, to){
while(true){
// 排序分区过程省略
// ...
if (to - bigBegin < smallEnd - from) {
quickSort(a, bigBegin, to);
to = smallEnd;
} else {
quickSort(a, from, smallEnd);
from = bigBegin;
}
}
}不得不说是一个很巧妙的实现。
相信看了本文案例你已经掌握了方法，更多精彩请关注php中文网其它相关文章！
推荐阅读：
Das obige ist der detaillierte Inhalt vonSo verwenden Sie die JS-Array-Sortiermethode. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
