总结前端排序中遇到的问题
前一轮似乎一直是一个误区：前端不能用于算法知识，长期以来，人们可能受到这种说法的影响。前端分类
前端排序场景
前端将排序条件作为请求参数传递给后端，后端将排序结果作为对前端的请求响应返回，这是一种常见的设计。
想象一个场景：如果你使用一个美食应用程序，你经常切换排序方式，然后按价格排序，然后按得分排序。
在实际生产中，受服务器成本等因素的制约。当单个数据查询成为整体性能的瓶颈时，它也将考虑通过在前端进行排序来优化性能。
排序算法
我觉得这是不必要的。作为计算机科学的基本算法，描述是维基百科的直接拷贝。
这一节的存在纯粹是为了（子）（子）（舒）。
javaｓｃｒｉｐｔ的排序
当涉及到前端分类，这是自然的第一个想到的Javaｓｃｒｉｐｔ的原生界面array.prototype.sort。
这个界面存在因为ECMAｓｃｒｉｐｔ第一版。让我们来看看最新的规范，它描述的是什么。
Array.prototype.sort规范
Array.prototype.sort（comparefn）
复制代码代码如下所示：
这个数组的元素被排序。排序是不稳定的（即元素相等不一定要是comparefn是保持原来的顺序）。不是未定义的，它应该是一个接受两个参数x和y的函数，如果x y返回一个负值。
很明显，规范并不限制排序算法内部实现的排序，甚至接口的实现不需要稳定地排序，这是一个关键点，它将涉及很多次。
在这种情况下，前端排序实际上依赖于各种浏览器的具体实现。那么，当今主流浏览器如何分类呢接下来，我们简单地比较Chrome，Firefox和微软边缘，分别。
实现在Chrome
Chrome的Javaｓｃｒｉｐｔ引擎是V8，因为它是开源的，您可以直接查看源代码。
整个array.js在Javaｓｃｒｉｐｔ语言实现。排序的方法显然是更复杂的比快速排序，已经看到，但很显然，核心算法仍然是一个快速排序的算法复杂度的原因是V8引擎性能的考虑，做了很多的优化。（下开放的展览）
实现在Firefox
目前还不可能确定Firefox Javaｓｃｒｉｐｔ引擎的数组排序算法目前将使用什么。{ 3 }
根据现有的信息，spidermoney内部归并排序的实现。
微软边缘的实现
对微软引擎，Javaｓｃｒｉｐｔ引擎的核心部分脉轮，已在2016年初GitHub开源。
通过对源代码的研究发现，查克拉的数组排序算法也是一种快速排序，与V8相比，它只实现了一种纯快速排序，没有任何性能优化的痕迹。
javaｓｃｒｉｐｔ数组排序问题
我们都知道，快速排序是一个不稳定的排序算法，和归并排序是稳定的排序算法。由于在不同的搜索引擎算法选择的差异，通过前端Javaｓｃｒｉｐｔ代码取决于array.prototype.sort接口，和分类的效果不一致的浏览器。
等级稳定性的不同要求特定的场景触发有问题；在许多情况下，这种不稳定性不会影响它。
如果在实际的项目开发中没有对数组的稳定性要求，我们可以看出，到目前为止，浏览器之间的区别并不那么重要。
但是，如果项目要求排序必须是稳定的，那么这些差异的存在就不能满足需要，我们需要为此做一些额外的工作。
例如 uff1a
一个城市的汽车牌照拍卖系统，投标的最终规则如下：
1。按价格分类；
2。相同的价格是按照投标顺序（即提交价格的时间）订购的。
如果排序是在前端，中标人在快速排序浏览器很可能是不符合预期。
探索差异的背后
在我们找到解决办法之前，有必要先探究问题的原因。
为什么Chrome使用快速排序
事实上，这种情况从一开始就存在。
Chrome测试版于2008年9月2日发布。然而，其发布后不久，有90人提交# bug反馈给开发组开发的铬。
这个bug问题讨论的时间跨度很大，直到2015年11月10日，仍有人对V8的数组排序实现问题发表评论。
同时，我们也注意到，这个问题已经关闭。然而，开发组的成员在2013年6月重开为ECMAｓｃｒｉｐｔ讨论下规范参考。
ES的最终结论是
复制代码代码如下所示：
它不会改变。稳定是不稳定的一个子集。和，子集，是，是，和其他因素。
/安德烈亚斯
本条前款规定，描述最终的ECMAｓｃｒｉｐｔ 2015规范。
时代特征
在对清规戒律，Chrome发布之初，据报道，这个问题可能有其特殊性。
如上所述，Chrome的第一个版本于2008年9月发布，根据StatCounter的统计，两个浏览器与当时市场占有率最高的是IE（当时只有IE6和IE7和Firefox），和市场占有率分别为67.16%和25.77%。也就是说，两个浏览器添加超过90%的市场份额。
根据另一个浏览器排序算法稳定性的统计数据，这两个超过90%的市场份额的浏览器采用了稳定的数组排序，因此在Chrome发行版开始时，开发者会受到质疑。
符合规范
在讨论bug问题的过程中，可以理解开发组成员用于快速排序引擎实现的一些考虑因素。
有一点，他们认为发动机必须符合ECMAｓｃｒｉｐｔ规范。因为不规范要求的稳定排序的描述，他们认为V8的实施是完全符合。
性能方面的考虑
此外，他们认为V8引擎设计中最重要的考虑因素之一是发动机的性能。
比归并排序更快，整体性能更好：
在实际的计算机执行环境中，快速排序比同一时间复杂度的排序算法（当最坏的组合遇到最坏的组合）快得多。
较低的空间开销，前者仅为O（n）空间复杂度，与运行时内存消耗较少的O（n）空间复杂度相比
V8阵列排序算法的性能优化
既然V8非常了解引擎的性能，那么它在数组排序中做什么呢
通过阅读源代码，一些皮毛得到了学习。
混合插入排序
快速排序是划分和管理、分解大型数组和逐层递归的思想，但是如果递归太深，递归调用堆栈的内存资源消耗将非常大，优化不好甚至可能导致堆栈溢出。
V8的当前实现是设置一个阈值，使用插入排序对小于10的最小数组进行排序。
根据代码注释，以及在维基百科的描述，而插入排序的平均时间复杂度（nsup2；O）为O（n）的快速排序，但在运行环境、小阵列使用插入排序比快速排序效率更高，而不再是展开。
V8引擎的代码示例
无功快速排序=函数QuickSort（，，到）{
......
当（真）{
短数组中插入排序更快。
如果（从< = 10）{
InsertionSort（，，等）；
返回；
}
......
}
......
}；
带他们
被称为快速排序的阿基里斯跟最坏的情况下，组合阵列算法退化。
快速排序算法的选择参考内核（支点），并分解为交换阵列为后续递归的两个数据的数据。如果一个已排序的数组，总是选择每个参考元素的第一个或最后一个元素，所以每次都会有一些地方是空的，递推数将达到N，导致算法的时间复杂度降低到O（nsup2；）。因此，支点的选择是非常重要的。
V8用于三（中位数为三）优化：除了两个附加元素，并在基准竞争元素中选择一个元素。
这第三个元素的选择策略大致如下：
当数组长度小于或等于1000时，元素的位置作为二进制元素的目标选择。
当数组的长度大于1000，每200-215（非固定，随着长度的数组元素）选择确定一批候选元素第一。然后一个候选元素的排序，和中值作为目标元素
最后，以三个元素的中值作为支点。
V8引擎的代码示例
无功getthirdindex =函数（，，到）{
无功t_array =新internalarray（）；
使用both'from'and'to/确定候选人的支点。
var增量= 200 +（（从）15）；
var j＝0；
从= 1；
到1；
对于（var i =；i <到；i =增量）{
t_array { } = {我J，一个{我} }；
++；
}
T_array.sort (function (a, b) {
返回comparefn（B一{ 1 }，{ 1 }）；
}）；
无功third_index = t_array { t_array.length > > 1 } { 0 }；
third_index返回；
}；
无功快速排序=函数QuickSort（，，到）{
......
当（真）{
......
如果（从- > 1000）{
third_index = getthirdindex（，，等）；
{人}
third_index = +（（-从）> > 1）；
}
}
......
}；
原地排序
当我回顾快速排序算法时，我在因特网上看到了许多使用Javaｓｃｒｉｐｔ的例子。
但是，发现大部分代码是按照以下方式实现的
无功快速排序=功能（ARR）{
如果（arr.length <= 1）{ return ARR；}
无功pivotindex = math.floor（arr.length / 2）；
VaR支点= arr.splice（pivotindex，1）{ 0 }；
var左}；
var；
对于（var i = 0；i < arr.length；i++）{
如果（ARR {我} <支点）{
Left.push（ARR {我}）；
其他{ }
Right.push（ARR {我}）；
}
}
返回快速排序（左），Concat（{转}，快速排序（右））；
}；
上述代码的主要问题是存储递归子阵在左、右两个数，因此，它需要额外的存储空间为O（n），空间复杂度理论平均（O N）相比差距较大。
额外的空间开销也影响到实际操作的整体速度，这也是其他排序算法的原因之一，这些排序算法可以在实际运行时快速地对性能进行排序，而不是在同一时间复杂度级别上进行排序。
V8源代码中的实现是对原始数组元素的交换。
为什么Firefox使用合并排序
它背后有一个故事。
事实上，Firefox在开始发布时不使用稳定的排序算法进行数组排序。这是一个有效的测试。
数组排序算法通过Firefox的原始版本的实现（火鸟）是一堆排序，这也是一个不稳定的排序算法。所以，后来有人提交一个bug。
Mozilla开发小组对这个问题进行了一系列的讨论。
我们可以从讨论的过程中得出几点意见。
1。同时，Mozilla的竞争对手是IE6。从上面的统计数据，它是已知的，IE6是一个稳定的排序。
布兰登·艾奇的父亲，2.javaｓｃｒｉｐｔ，感觉稳定性OD
3、在使用堆排序之前，Firefox是一种快速排序。
在此基础上，开发组的成员往往会达到一个稳定的排序算法的前提下，Firefox3是一种新的数组排序的实现。
解决排序稳定性的差异
到目前为止，我想讨论一下排序实现中浏览器之间的区别以及它们存在的原因。
但在这里阅读，读者可能还有一个问题：如果我的项目是依靠一个稳定的排序
解决方案
事实上，解决这个问题的想法比较简单。
浏览器为不同的考虑选择不同的排序算法，有些可能偏向于追求极端性能，有些则偏向于提供良好的开发经验，但有一些规则需要遵循。
从目前已知的情况下，所有的主流浏览器（包括IE6，7, 8）基本上都是枚举数组的排序算法的实现：
1。归并排序 / timsort
2。快速排序
所以，我们将快速排序，通过自定义转换，成为一个稳定的排序，不是吗
一般来说，对数组对象使用不稳定排序会影响结果。使用稳定排序或不稳定排序的其他类型数组的结果是相等的：
对经过排序的数组进行预处理，以将自然顺序属性添加到要排序的每个对象，它不与对象的其他属性相冲突。
自定义分类比较的方法，comparefn，总是以自然秩序为二判断维度的预断是相等的。
在归并排序方面，由于算法本身是稳定的，所以该算法是稳定的。附加自然序比较不改变排序结果，因此方案相容性较好。
但它需要修改要排序的数组，还需要为存储自然顺序属性创建额外的空间。可以想象，V8引擎不应该采用类似的方法，但是，开发人员自定义排序方案是可行的。
程序代码实例
严格使用；
const指数=符号（'index）；
功能getcomparer（比较）{
返回函数（左，右）{
让结果比较（左，右）；
返回结果左{ } -右} { index }：结果= 0；
}；
}
函数排序（数组，比较）{
阵列= Array.map（
（项目，索引）{ {
如果（typeof项目= 'object）{
项目{索引} =索引；
}
返回的项目；
}
）；
返回array.sort（getcomparer（比较））；
}
以上只是一个满足稳定排序的算法的简单示例。
原因很简单，因为数据结构作为一个杂数组输入实际的生产环境，需要根据实际情况确定需要在排序前进行更多种类的检测。
标注
1。前端是一个比较宽泛的概念，本文的前端主要指的是使用浏览器作为载体的环境和Javaｓｃｒｉｐｔ作为编程语言的环境。
2。本文不打算涉及整个算法，我们使用普通排序算法作为切入点。
三.这类的错误spidermoney相关搜索当算法被证实是通过Firefox的数组排序的实现。这是讨论建议使用timsort算法在极端条件下的过程中，更好的性能取代归并，但Mozilla的工程师说，timsort算法具有许可证授权的问题，没有办法在Mozilla软件直接使用算法，随后等待答复
总结
以上是对前端排序中遇到的问题的总结和解决方法。近年来，越来越多的项目转变为富客户端应用的方向，并在项目前端的比例更大。未来随着浏览器的计算能力的进一步增强，它允许一个更复杂的计算。有责任感的变化，有可能是在前面最终形成的一些重大变化。行走江湖，总是有一个技能。