摘要：快速排序是不稳定的排序算法。浏览器的实现不同有什么影响排序算法不稳定有什么影响举个例子某市的机动车牌照拍卖系统，最终中标的规则为按价格进行倒排序相同价格则按照竞标顺位即价格提交时间进行正排序。
本文要解决的问题
Array.prototype.sort 各浏览器的算法实现1、找出 Array.prototype.sort 使用的什么排序算法
2、用一种直观的方式展示 Array.prototype.sort 的时间复杂度，看看它有多快？
3、实际开发中要注意的问题
ECMAScript 5.1
ECMAScript 6.0
ECMAScript 草案
看完上面三个规范中 Array.prototype.sort 部分，我们会发现 ECMAScript 不同版本规范对 Array.prototype.sort 的定义中没有要求用什么样的排序方式实现 sort() 方法，也没有要求是否要采用稳定排序算法（下文会解释什么是稳定排序算法）。
因此各浏览器都给出自己的实现方式：
表格内容部分来自于维基百科
| 浏览器 | 使用的 JavaScript 引擎 | 排序算法 | 源码地址 |
|---|---|---|---|
| Google Chrome | V8 | 插入排序和快速排序 | sort 源码实现 |
| Mozilla Firefox | SpiderMonkey | 归并排序 | sort 源码实现 |
| Safari | Nitro（JavaScriptCore ） | 归并排序和桶排序 | sort 源码实现 |
| Microsoft Edge 和 IE(9+) | Chakra | 快速排序 | sort 源码实现 |
V8 引擎的一段注释
// In-place QuickSort algorithm. // For short (length <= 10) arrays, insertion sort is used for efficiency.
Google Chrome 对 sort 做了特殊处理，对于长度 <= 10 的数组使用的是插入排序(稳定排序算法) ，>10 的数组使用的是快速排序。快速排序是不稳定的排序算法。
但是很明显比我们常见的快速排序要复杂得多，不过核心算法还是快速排序。算法复杂的原因在于 v8 出于性能考虑进行了很多优化。
再看 safari Nitro 引擎的一段代码
if (typeof comparator == "function")
comparatorSort(array, length, comparator);
else if (comparator === null || comparator === @undefined)
stringSort(array, length);
省略....
function stringSort(array, length)
{
var valueCount = compact(array, length);
var strings = @newArrayWithSize(valueCount);
for (var i = 0; i < valueCount; ++i)
strings[i] = { string: @toString(array[i]), value: array[i] };
bucketSort(array, 0, strings, 0);
}
省略....
function comparatorSort(array, length, comparator)
{
var valueCount = compact(array, length);
mergeSort(array, valueCount, comparator);
}
默认使用的桶排序，如果 sort 传入的自定义函数作为参数，就是用归并排序（稳定排序算法）
Firefox 源码就不贴了，上面的表格有源码地址，使用的稳定排序算法 — 归并算法。
Microsoft Edge 和 IE(9+) 使用的不稳定排序算法 - 快速排序。
但是 IE（6、7、8）使用的稳定算法。
| 排序类型 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 | |
|---|---|---|---|---|---|---|
| 快速排序 | O(nlogn) | O(nlogn) | O(n²) | O(nlogn) | 不稳定 | |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | |
| 插入排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 | |
| 桶排序 | O(n+k) | O(n+k) | O(n²) | O(n+k) | (不)稳定 | |
注: 桶排序的稳定性取决于桶内排序的稳定性, 因此其稳定性不确定。
算法时间复杂度
在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数， 进而分析T(n)随着n的变化情况并确定T(n)的数量级。 算法的时间复杂度，也就是算法的时间度量，记作：T(n)=O(f(n))。 它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同， 称作算法的时间复杂度，简称为时间复杂度。 其中f(n)是问题规模n的某个函数。
常用的时间复杂度所耗费的时间从小到大依次是
O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2^n) < O(n!) < O(n^n)
图片来源
算法的时间复杂度与运行时间有一些常见的比例关系 查看图表来源
| 复杂度 | 10 | 20 | 50 | 100 | 1,000 | 10,000 | 100,000 | |
|---|---|---|---|---|---|---|---|---|
| O(1) | < 1s | < 1s | < 1s | < 1s | < 1s | < 1s | < 1s | |
| O(log(n)) | < 1s | < 1s | < 1s | < 1s | < 1s | < 1s | < 1s | |
| O(n) | < 1s | < 1s | < 1s | < 1s | < 1s | < 1s | < 1s | |
| O(n*log(n)) | < 1s | < 1s | < 1s | < 1s | < 1s | < 1s | < 1s | |
| O(n²) | < 1s | < 1s | < 1s | < 1s | < 1s | 2 s | 3-4 min | |
| O(n³) | < 1s | < 1s | < 1s | < 1s | 20 s | 5 hours | 231 days | |
| O(2^n) | < 1s | < 1s | 260 days | hangs | hangs | hangs | hangs | |
| O(n!) | < 1s | hangs | hangs | hangs | hangs | hangs | hangs | |
| O(n^n) | 3-4 min | hangs | hangs | hangs | hangs | hangs | hangs | |
维基百科关于算法稳定性的解释
当相等的元素是无法分辨的，比如像是整数，稳定性并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。
(4, 1) (3, 1) (3, 7)（5, 6）
在这个状况下，有可能产生两种不同的结果，一个是让相等键值的纪录维持相对的次序，而另外一个则没有：
(3, 1) (3, 7) (4, 1) (5, 6) (维持次序） (3, 7) (3, 1) (4, 1) (5, 6) （次序被改变）
想看自己浏览器排序算法的稳定性？ 点我
各种排序算法实现有多快？我们先通过这个在线网站大体测试一下
对一个有 10000 个元素的数组，快速排序 > 归并排序 >>> 插入排序
而且插入排序大于 1s 了。
对于一个只有 10 个元素的数组，插入排序 > 快速排序
这也说明了为什么 chrome 在小于等于 10 个元素的小数组使用插入排序的原因了。
排序算法不稳定有什么影响
举个例子：
某市的机动车牌照拍卖系统，最终中标的规则为：
1、按价格进行倒排序；
2、相同价格则按照竞标顺位（即价格提交时间）进行正排序。
排序若是在前端进行，那么采用快速排序的浏览器中显示的中标者很可能是不符合预期的。
解决办法
Array.prototype.sort 在不同浏览器中的差异和解决办法
大体的思路就是，自己写一个稳定的排序函数，以保持各浏览器的一致性。
工具1、在线排序算法对比网站
2、排序算法视觉图
1、快速排序（Quicksort）的Javascript实现
2、JS中可能用得到的全部的排序算法
3、7 种常用的排序算法-可视化
4、深入了解javascript的sort方法
5、JavaScript 排序算法汇总
聊聊前端排序的那些事
排序算法
JavaScript排序算法汇总
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/87289.html
摘要：上一篇数据结构与算法树写在前面这是学习数据结构与算法的最后一篇博客，也是在面试中常常会被问到的一部分内容排序和搜索。 上一篇：JS数据结构与算法_树 写在前面 这是《学习JavaScript数据结构与算法》的最后一篇博客，也是在面试中常常会被问到的一部分内容：排序和搜索。在这篇博客之前，我每每看到排序头就是大的，心里想着类似冒泡排序，两层遍历啪啪啪就完事了，然后再也无心去深入研究排序相...
摘要：关于我的博客掘金专栏路易斯专栏原文链接深度长文数组全解密全文共字，系统讲解了数组的各种特性和。构造器构造器用于创建一个新的数组。中声明的数组，它的构造函数是中的对象。 本文首发于CSDN网站，下面的版本又经过进一步的修订。 关于 我的博客：louis blog 掘金专栏：路易斯专栏 原文链接：【深度长文】JavaScript数组全解密 全文共13k+字，系统讲解了JavaScrip...
摘要：方法可以接受一个可选的参数，比较回调函数。方法会修改原本数组输出如上，在调用方法后，自身数组被修改。对于长数组会使用快速排序，而快速排序一般是不稳定的。所以方法返回的数组永远是该方法认为的升序数组。 前几天在某公司面试的时候被问到关于这个方法的默认值的问题（然而面试官跟我说的其实是错的，当场我还不够底气去反驳）。突然发现对这个方法的了解还不够，因此回来查了资料，看了v8引擎的实现和EC...
摘要：函数作为参数情况，，和是中内置的高阶函数。知道了到底啊什么是高阶函数，有哪些类型的高阶函数。公众号技术栈路线大家好，我是，公众号程序员成长指北作者，这篇文章是必知必会系列的高阶函数讲解。 前言 一道经典面试题： //JS实现一个无限累加的add函数 add(1) //1 add(1)(2) //3 add(1)(2)(3) //6 当大家看到这个面试题的时候，能否在第一时间想到...
摘要：基础构造函数以下几种排序算法做为方法放在构造函数里。代码图解选择排序选择排序算法是一种原址比较排序算法。它的性能通常比其他的复杂度为的排序算法要好。代码划分过程图解排序没有定义用哪个排序算法，所以浏览器厂商可以自行去实现算法。 基础构造函数 以下几种排序算法做为方法放在构造函数里。 function ArrayList () { var array = []; // 交换位置...
阅读 750·2021-11-17 09:33
阅读 312·2019-08-30 11:16
阅读 2380·2019-08-29 16:05
阅读 3239·2019-08-29 15:28
阅读 1289·2019-08-29 11:29
阅读 1827·2019-08-26 13:51
阅读 3274·2019-08-26 11:55
阅读 1082·2019-08-26 11:31
