浅谈Array的sort方法

2017-10-24

JavaScript array.sort(compare()) 的实现原理是什么？

先看下’ 2015-ECMAScript-262语言规范 ‘的解释：The sort is not necessarily stable - 排序是不稳定的. (Ps: 截取的重要部分）.

MDN的基本解释：sort() 方法在适当的位置对数组的元素进行排序，并返回数组。 sort 排序不一定是稳定的。默认排序顺序是根据字符串Unicode码点.

基本的就不说了，那怎样才算排序不稳定？我们做个小实验：

<span style="font-family:Tahoma;font-size:14px;">var exArray = [15,0,-3,5];  
var i=1;  
window.onload = function(){  
exArray.sort(compare);  
console.log("最终结果"+exArray);  
}  
function compare(num1,num2){  
console.log("第" + (i++) +"次比较： "+"nowArray:["+ exArray + "].  参数num1: "+num1+"， 参数num2: "+num2);  
var key = (num1 > num2) ? 1:-1;  
console.log(key);  
return key;  
}</span>

运行结果解释：

第一次比较时数组元素为：15,0，-3,5. compare比较函数的参数为：15,0. 因为返回1，所以0和15互换位置.
第二次比较时数组元素为：0,15，-3,5. compare比较函数的参数为：15，-3. 因为返回1，所以按道理15和-3互换.
第三次比较时发现数组元素为：0，15,15,5. -3被拐跑了？这里便体现了”不稳定排序”. 15和-3比较后并没有立即互换，首先把15赋给arr[2]数组元素，然后把 -3(可能) 存放在某个临时变量中，再与前面的0做比较，当确定-3比0小之后，互换位置，释放临时变量.
第四次比较时数组元素理所当然的变成了-3,0,15,5. 此时compare比较函数的参数为：15,5.
第五次的比较和第三次原理相同.
得到最终的排序数组：-3,0,5,15.

那做完这个小实验可以总结出一些可能不太严谨的规律：

数组sort比较时，从数组内索引值为0和1的参数开始比较（即参数num1和num2），比较结果没有变动的话，继续比较索引值1和2的，如果结果有变化，变换两者的位置（索引值），并判断之前有无其他参数，如果有的话则会对参数num1和num1之前的参数进行比较。如果没有则用参数num2与索引值+1的参数比较。遵循此逻辑重复循环操作，完成排序.

未完待续。。。。