Cette fois, je vais vous montrer comment utiliser la méthode de tri par tableau JS. Quelles sont les précautions lors de l'utilisation de la méthode de tri par tableau JS. Ce qui suit est un cas pratique, jetons un coup d'œil.
Dans la classe d'algorithmes, nous serons exposés à de nombreux types d'algorithmes de tri, tels que le tri à bulles, le tri par sélection, le tri rapide, le tri par tas, etc. Alors, quel algorithme de tri la méthode de tri de javascript utilise-t-elle ? Pour comprendre cela, il suffit de regarder le code source de la v8. L'implémentation d'Array.sort dans la v8 est réalisée à l'aide de JavaScript. En un coup d'œil, il utilise l'algorithme de tri rapide, mais il est évidemment plus compliqué que le tri rapide que nous connaissons. Alors, quelle est exactement la complexité ? Pourquoi rendre les choses si compliquées ? C’est la question que nous allons explorer aujourd’hui.
Algorithme de tri rapide
L'algorithme de tri rapide est appelé algorithme de tri rapide car il peut atteindre une complexité temporelle optimale et moyenne de O(nlogn ), est un algorithme très largement algorithme de tri utilisé. Son principe n'est pas compliqué. Trouvez d'abord un élément de référence (pivot, n'importe quel élément peut être utilisé), puis comparez tous les éléments avec l'élément pivot, mettez-les dans un ensemble et mettez les autres. dans un autre ensemble, puis effectuez un tri rapide sur ces deux ensembles, et obtenez enfin une séquence complètement triée.
L'essentiel du tri rapide consiste donc à découper en continu le tableau d'origine en petits tableaux, puis à effectuer le même traitement sur les petits tableaux. Il s'agit d'une idée typique de conception d'algorithme diviser pour régner. Implémenter un algorithme simple de tri rapide n’est pas difficile. Essayons :
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));
}Il s'agit d'une implémentation très basique, sélectionnant le premier élément du tableau comme élément de base.
Tri sur place
Nous pouvons remarquer que dans l'algorithme ci-dessus, nous créons en fait un nouveau tableau comme résultat du calcul, à partir de ce qui n'est pas économique du point de vue de l'utilisation de l'espace perspective. L'algorithme de tri rapide JavaScript ne crée pas de nouveau tableau comme le code ci-dessus, mais trie les éléments en échangeant les positions des éléments en fonction du tableau d'origine. Par conséquent, à l'instar des méthodes push, pop et splice, la méthode de tri modifiera également l'objet tableau d'origine !
Comme nous l'avons déjà dit, l'essentiel du tri rapide est de couper le tableau. Donc, si vous échangez simplement des éléments sur le tableau d'origine, comment couper le tableau ? C'est très simple, nous n'avons pas besoin de couper le tableau, nous devons juste nous souvenir des numéros d'index de début et de fin de chaque partie. Par exemple, supposons qu'il existe un tableau [12, 4, 9, 2, 18, 25] et que le premier élément 12 est sélectionné comme élément de base. Ensuite, selon l'algorithme de tri rapide d'origine, le tableau sera coupé en deux. petits tableaux : [4, 9, 2], 12, [18, 25]. Mais on ne peut pas non plus le couper, modifier d'abord le tableau d'origine en [4, 9, 2, 12, 18, 25] en comparant et en échangeant des éléments, puis en fonction de la position de l'élément de référence 12, on pense que les éléments 0~2 sont un groupe, les éléments n°4~5 sont un groupe Pour faciliter l'expression, j'appelle ici la partition composée d'éléments plus petits que l'élément de référence la partition décimale, et l'autre partition est appelée la partition des grands nombres. . Ceci est très similaire au partitionnement du disque dur d'un ordinateur. Il ne divise pas vraiment le disque dur en lecteur C et lecteur D, mais enregistre certaines positions de début et de fin et le divise logiquement en plusieurs partitions. De même, dans l’algorithme de tri rapide, nous appelons également ce processus partition. En conséquence, je dois modifier ma déclaration précédente. Le cœur de l'algorithme de tri rapide est le partitionnement.
Cela dit, implémentons un tri rapide avec des partitions :
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;
}Il semble que le code soit beaucoup plus long, mais ce n'est pas trop compliqué. Tout d'abord, puisqu'il s'agit d'échange d'éléments de tableau, nous implémentons d'abord une méthode swap pour gérer l'échange d'éléments. Dans l'algorithme de tri rapide, deux paramètres sont ajoutés, from et to, qui indiquent respectivement quelle partie du tableau est actuellement traitée à partir de l'index de début et to est l'index de fin si ces deux paramètres sont manquants, cela signifie un traitement. l'ensemble du tableau.
同样的，我用最简单的方式选取基准元素，即所要处理分区的第一个元素。然后我定义了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中文网其它相关文章！
推荐阅读：
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
