引例
首先看一段代码：
<html><head><title>sort稳定性</title></head><body>
<h1>Non-stable Sort</h1>
<ol>
<script type="text/javascript">
function Pair(_x, _y)
{
this.x = _x;
this.y = _y;
}
function pairSort(a, b)
{
return a.x - b.x;
}
var check = new Array(new Pair("1", "1"), new Pair("1", "2"),
new Pair("1", "3"), new Pair("1", "4"),
new Pair("2", "1"), new Pair("2", "2"),
new Pair("2", "3"), new Pair("2", "4"));
check.sort(pairSort);
for (var i = 0; i < check.length; ++i)
{
document.write("<li>" + check[i].x + ", " + check[i].y + "</li>\n");
}
</script>
</ol>
</body></html>
会输出什么 ？
答案
ie ,firefox3 :
1. 1, 1
2. 1, 2
3. 1, 3
4. 1, 4
5. 2, 1
6. 2, 2
7. 2, 3
8. 2, 4
firefox 2:
1. 1, 1
2. 1, 2
3. 1, 4
4. 1, 3
5. 2, 2
6. 2, 1
7. 2, 3
8. 2, 4
chrome:
1. 1, 2
2. 1, 4
3. 1, 3
4. 1, 1
5. 2, 2
6. 2, 4
7. 2, 3
8. 2, 1
解释
这就涉及到了 sort 各个浏览器是如何实现的 ，ecma没有规定 sort的具体实现 ，对稳定性也没有要求 :
15.4.4.11 Array.prototype.sort (comparefn)
The elements of this array are sorted. The sort is not necessarily stable
(that is, elements that compare equal do not necessarily remain in their
original order).
，而上述结果正是由于各个浏览器选择了不同的排序算法，各个算法的稳定性不同而导致了结果的差异。
firefox2采取了不稳定的堆排序，firefox3采用了稳定的归并排序
，ie 速度较慢，具体算法不明，可能为冒泡或者插入排序，而chrome则为了最大效率，采用了两种算法：
chrome use quick sort for a large dataset ( >22) ,and for a smaller
dataset (<=22) chrome use insert sort but modified to use binary
search to find insert point ,so traditionally insert sort is stable
,but chrome make it faster and unstable , in conclusion chrome’s sort
is quick and unstable .
chrome的具体实现可以直接 document.writeln(Array.prototype.sort) 得到。
所以依赖于sort稳定性的应用需要自己写排序算法了，不要贸然使用系统的 Array.prototype.sort 。
理论基础：
什么是稳定性
就是两个元素具有相同的key，依据key排序后，相同key的两个元素的相对位置不变。
如 ：
3 ,7 ,1(1) ,8 ,1(2),6
得到这样的排序才算是稳定的排序算法 ：
1(1) , 1(2) ,3 ,6 ,7 ,8
各个算法稳定性列举：
冒泡排序：
基础为两两相邻元素比较，所以相同的两个相邻元素不会交换位置，所以稳定。
选择排序：
每次选择一个当前位置以后最小的一个，和当前位置交换，可能不稳定。
如：
10(1) , 9 , 10(2) ,1
第一轮过后：
1 ,9 ,10(2) ,10(1)
插入排序：
在前面有序的基础上，再将当前元素插入到前面合适的位置，只有当前元素比前面序列中某个位置元素大时才能插入，稳定，
例如：
10 , 1(1) ,1(2) ,2,5
->
1(1) ,10,1(2),2,5
->
1(1),1(2),10,2,5
快速排序：
同选择排序，类似有个长距离选择交换的过程，选择了一个pivot元素，则pivot和他应该在的位置的元素交换，可能破坏稳定性。
例如：
3 ,1(1) ,1(2) ,4
pivot
->
1(2) ,1(1) ,3,4
归并排序：
是两个相邻序列进行合并，合并时我们保证相同的元素出现时，前一个序列的元素出现在前面。
例如：
1(1) ,10 + 1(2),9 = 1(1) ,1(2),9,10
基数排序：
从低位到高位，每一轮都是用稳定排序算法排序，则结果是稳定的。
希尔插入排序：
由于有gap的存在，可能插入元素中间会破坏稳定性。
例如：
| 3, 1(1), 1(2) | |1(3) ,4 ,4|
->
| 1(3) ,1(1) ,1(2) | | 3 ,4 ,4 |
堆排序：
父节点之间进行选择时，可能会破坏稳定性，
例如下面两堆
1
10(1) 9
11 10(2)
1
9 10(1)
11 10(2)
最终必有一堆最终结果会破坏稳定性，有兴趣可以自己推导。
分享到：
相关推荐
array.prototype.at 符合ESnext规范的Array.prototype.at / polyfill / replacement可以使用到ES3。 该软件包实现了接口。 它在ES3支持的环境中工作，并符合建议的。 因为Array.prototype.at依赖于接收方（ this...
array.prototype.flatmap 符合ESnext规范的Array.prototype.flatMap填充程序/ polyfill / replacement可以使用到ES3。 该软件包实现了接口。 它在ES3支持的环境中工作，并符合建议的。 因为Array.prototype.flatMap...
array.prototype.values 符合ES2015规范的Array.prototype.values匀场/填充/替换值可一直使用到ES3。 该软件包实现了接口。 它可以在ES3支持的环境中工作并符合。 因为Array.prototype.values取决于接收方（“ ...
array.prototype.flat 符合ES2019规范的Array.prototype.flat填充/填充/替换，可向下使用到ES3。 该软件包实现了接口。 它在ES3支持的环境中工作，并符合建议的。 因为Array.prototype.flat依赖于接收方（ this值）...
代码如下: function test(){ //将参数转为一个数组 var args = Array.prototype.slice.apply(arguments); alert(args); } arguments在JavaScript语法中是函数特有的一个对象属性(Arguments对象)，用来...
发现大多人都用了Array.prototype.slice.call(argments,0)，一直不明白这句是干什么的。而昨天温习了slice()方法，再参考Function.call(thisArg[, arg1[, arg2[, ...]]])，还是不得而知（我脑筋转得慢:|）。
array.prototype.indexof 符合ES2015规范的shim / polyfill / replacement的Array.prototype.indexof ，可工作到ES3。 该软件包实现了接口。 它可以在ES3支持的环境中工作并符合。 因为Array.prototype.indexOf...
Array没有indexOf方法，这样在一个数组中查找某个元素的索引时比较麻烦，为了调用方便，于是通过prototype原型扩展了Array.prototype.indexOf()，这样用起来就比较方便了。但是这个自定义的indexOf在对数组进行遍历...
array.prototype.map 符合ES5规范的Array.prototype.map填充程序/ polyfill / replacement可以使用到ES3。 该软件包实现了接口。 它可以在ES3支持的环境中工作并符合。 因为Array.prototype.map依赖于接收方（“ ...
数组包含 符合ES7 / ES2016规范的Array.prototype.includes / polyfill / replacement可以使用到ES3。 该软件包实现了接口。 它在ES3支持的环境中工作，并符合建议的。 因为Array.prototype.includes依赖于接收方（ ...
array.prototype.entries 符合ES2015规范的Array.prototype.entries / polyfill / replacement可以使用到ES3。 该软件包实现了接口。 它可以在ES3支持的环境中工作并符合。 因为Array.prototype.entries依赖于...
array.prototype.reduceRight 符合ES5规范的Array.prototype.reduceRight填充/填充/替换功能，其工作范围可追溯到ES3。 该软件包实现了接口。 它可以在ES3支持的环境中工作并符合。 因为Array.prototype....
array.prototype.lastindexof 符合ES2015规范的shim / polyfill / replacement的Array.prototype.lastindexof ，可向下使用到ES3。 该软件包实现了接口。 它可以在ES3支持的环境中工作并符合。 因为Array....
array.prototype.keys 符合ES2015规范的Array.prototype.keys shim / polyfill / replacement可以使用到ES3。 该软件包实现了接口。 它可以在ES3支持的环境中工作并符合。 因为Array.prototype.keys依赖于接收方（...
array.prototype.copywithin 符合ES2015规范的Array.prototype.copyWithin填充板/填充/替换，可向下运行到ES3。 该软件包实现了接口。 它可以在ES3支持的环境中工作并符合。 因为Array.prototype.copyWithin依赖...
js代码-面试题---Array.prototype.sort() 底层原理,事件捕获与冒泡理解
符合ES5规范的Array.prototype.every / polyfill / replacement可以使用到ES3。 该软件包实现了接口。 它在ES3支持的环境中工作，并符合建议的。 因为Array.prototype.every取决于接收方（“ this”值），所以...
Array没有indexOf方法，这样在一个数组中查找某个元素的索引时比较麻烦，为了调用方便，于是通过prototype原型扩展了Array.prototype.indexOf()，这样用起来就比较方便了。但是这个自定义的indexOf在对数组进行遍历...
永远不要写Array.prototype.slice.call(arguments); 以后再！ 这是基于但使用Object.defineProperty(arguments.constructor.prototype, [functionName], {enumerable: false, configurable: true, value: [function...