JavaScript数组排序方法sort()深层探究
—— sort()方法的算法分析及奇怪现象总结
案发现场还原
今天突然发现之前写的一个javascript数组排序的功能出问题了，如下：
简化版案发现场：
//对一个由 A0 至 A9 共10个元素组成的乱序数组进行排序
var source = ['A7', 'A6', 'A0', 'A8', 'A5', 'A3', 'A4', 'A1', 'A9', 'A2'];
source.sort(function(a, b){
return a > b;
});
/*
* 结果为：
* ["A0", "A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8", "A9"]
*/
//对一个由 A0 至 B0 共11个元素组成的乱序数组进行排序
var source = ['A7','A6','A0','A8','A5','A3','A4','A1','A9','A2','B0'];
source.sort(function(a, b){
return a > b;
});
/*
* 结果为：
* ["A3", "A7", "A0", "A2", "A5", "A6", "A4", "A1", "A8", "A9", "B0"]
*/
怎么样！怕不怕！！！服不服！！！不管你服不服，我反正是怕了。。。
案件规律分析及总结：
经过反复测试：
- 当数组长度小于等于10的时候，有参数的
.sort(sortby)方法排序正常；- 当数组长度大于10的时候，有参数的
.sort(sortby)方法排序会出现错乱；- 当有参数的
.sort(sortby)方法排序出现错乱时，多次执行该方法每次的结果都不相同；- 不论数组长度多长，无参数的
.sort()方法排序始终正常。
.sort() 方法定义及排序错误的解决方案
.sort() 方法用于对数组的元素进行排序。
语法
arrayObject.sort(sortby)
| 参数 | 描述 |
|---|---|
| sortby | 可选。规定排序顺序。必须是函数。 |
返回值
对数组的引用。请注意，数组在原数组上进行排序，不生成副本。
说明
如果调用该方法时没有使用参数，将按字母顺序对数组中的元素进行排序，说得更精确点，是按照字符编码的顺序进行排序。要实现这一点，首先应把数组的元素都转换成字符串（如有必要），以便进行比较。
如果想按照其他标准进行排序，就需要提供比较函数，该函数要比较两个值，然后返回一个用于说明这两个值的相对顺序的数字。比较函数应该具有两个参数 a 和 b，其返回值如下：
- 若 a < b，在排序后的数组中 a 应该出现在 b 之前，则返回一个小于 0 的值。
- 若 a == b，则返回 0。
- 若 a > b，则返回一个大于 0 的值。
解决方案
那么，其实看完定义，聪明的小伙伴就已经知道为什么我们的排序会出现错误了：
.sort() 方法规定，作为其参数的 function(a, b) 的返回值必须为数值类型（负数、0、正数分别代表a < b、a == b和a > b）
而我们在上面的代码中返回的确是 bool 类型，这显然是不对的，bool类型只有true/false两个值，怎么可能表达出 大于/小于/等于 3种状态呢。大家都知道在js里面 true == 1 false == 0 这两个表达式是成立的，也就是说，在上面的错误代码中，虽然本意可能是说返回false就代表 a < b,但实际执行起来程序却会认为 a == b，这也就是排序结果错误的原因。
所以，其实正确的代码应该是这样的：
source.sort(function(a, b){
if(a == b)
return 0;
return a > b ? 1 : -1;
});
事实证明，这样确实已经可以得到正确的排序结果了，不论数组长度有多长，结果都是正确的。
.sort() 方法深层探究[1]: 排序算法分析
为了分析javascript中的.sort() 方法中使用的排序算法，我们可以在sortby函数内加上一些日志，如下：
代码、执行日志及日志分析内容较长，可以直接看后面的分析结果。
var source = ['A1', 'A9', 'A0', 'A5', 'A3', 'A2', 'A7', 'A8', 'A4', 'A6'];
var sortby = function (a, b) {
console.log(source);
console.log('-----------------------------------------------------------');
console.log('compare: ' + a + '\t' + b);
var result = 0;
if(a > b)
result = 1;
if(a < b)
result = -1;
console.log('result : ' + result);
return result;
};
source.sort(sortby);
/*
* 输出日志及分析如下：
*
* ["A1", "A9", "A0", "A5", "A3", "A2", "A7", "A8", "A4", "A6"]
* -----------------------------------------------------------
* compare: A1 A9
* result : -1
* ["A1", "A9", "A0", "A5", "A3", "A2", "A7", "A8", "A4", "A6"]
* 分析：第一步，比较[0][1]两个元素并排序，看起来像是冒泡排序。
* -----------------------------------------------------------
* compare: A9 A0
* result : 1
* ["A1", "A9", "A9", "A5", "A3", "A2", "A7", "A8", "A4", "A6"]
* 分析：第二步，比较[1][2]两个元素并排序。
* 疑①：结果有些奇怪，按照冒泡排序的话理应将[1][2]两个元素调换位置变成[2][1]，
* 但这里确是[1][1]，感觉应该是将[2]保存到临时变量中了，然后将[1]赋值给了[2]，
* 所以，这里应该是一个中间状态，这一步操作没有完成。
* -----------------------------------------------------------
* compare: A1 A0
* result : 1
* ["A0", "A1", "A9", "A5", "A3", "A2", "A7", "A8", "A4", "A6"]
* 分析：第三步，按照上面的冒泡推断，将临时变量中的[2]赋值给了[1]。
* 疑②：这一步与上一步应该可以一步完成，不知道为什么用了两步。
* -----------------------------------------------------------
* compare: A9 A5
* result : 1
* ["A0", "A1", "A9", "A9", "A3", "A2", "A7", "A8", "A4", "A6"]
* 分析：第四步，比较[2][3]两个元素并排序。
* 疑③：同①，产生了相同元素，并将[3]保存到临时变量中。
* -----------------------------------------------------------
* compare: A1 A5
* result : -1
* ["A0", "A1", "A5", "A9", "A3", "A2", "A7", "A8", "A4", "A6"]
* 分析：第五步，比较[2][3]两个元素并排序，初步断定为冒泡排序，因为疑点的存在，可能为变种。
* 疑④：同②，利用两步完成了冒泡排序中的一步。
* -----------------------------------------------------------
* compare: A9 A3
* result : 1
* ["A0", "A1", "A5", "A9", "A9", "A2", "A7", "A8", "A4", "A6"]
* 分析：第六步，比较[3][4]两个元素并排序。
* 疑⑤：同③，产生了相同元素，并将[4]保存到临时变量中。
* -----------------------------------------------------------
* compare: A5 A3
* result : 1
* ["A0", "A1", "A5", "A5", "A9", "A2", "A7", "A8", "A4", "A6"]
* 分析：第七步，比较[2]与临时变量中的[4]，并将[2]存入临时变量中并将[2][3]都变成了[2]。
* 疑⑥：按照冒泡排序，应该直接调换[3][4]两个元素的位置就好了（即使上面用了两步完成这个调换操作），
* 但是这里将临时变量中的[4]与不相关的[2]做比较就有些奇怪了
* -----------------------------------------------------------
* compare: A1 A3
* result : -1
* ["A0", "A1", "A3", "A5", "A9", "A2", "A7", "A8", "A4", "A6"]
* 分析：第八步，至此到[4]之前都已经排序完成，虽然上面异步操作有点奇怪。
* -----------------------------------------------------------
* compare: A9 A2
* result : 1
* ["A0", "A1", "A3", "A5", "A9", "A9", "A7", "A8", "A4", "A6"]
* 分析：第九步，比较[4][5]两个元素，产生了相同元素，并将[5]保存到临时变量中，一直在重复这个奇怪的操作。
* -----------------------------------------------------------
* compare: A5 A2
* result : 1
* ["A0", "A1", "A3", "A5", "A5", "A9", "A7", "A8", "A4", "A6"]
* 分析：第十步，比较[3]和临时变量中的[5]。这就有意思了，为什么要去跟[3]比较呢？[3]有什么特殊的地方吗？
* 确实，仔细看我们就会发现[0][1][2][3][4]现在都是有序的，而[3]正好处于中间位置，
* 这让我们不由得联想到二分法，再结合上面的第七步，果然也符合这个推断，确实是使用了二分法。
* 这也解释了为什么在一至六步中会使用两步来完成调换操作，其实并不是简单的调换，
* 而是使用了一次二分法插入排序。
* -----------------------------------------------------------
* compare: A3 A2
* result : 1
* ["A0", "A1", "A3", "A3", "A5", "A9", "A7", "A8", "A4", "A6"]
* -----------------------------------------------------------
* compare: A1 A2
* result : -1
* ["A0", "A1", "A2", "A3", "A5", "A9", "A7", "A8", "A4", "A6"]
* -----------------------------------------------------------
* compare: A9 A7
* result : 1
* ["A0", "A1", "A2", "A3", "A5", "A9", "A9", "A8", "A4", "A6"]
* -----------------------------------------------------------
* compare: A5 A7
* result : -1
* ["A0", "A1", "A2", "A3", "A5", "A7", "A9", "A8", "A4", "A6"]
* -----------------------------------------------------------
* compare: A9 A8
* result : 1
* ["A0", "A1", "A2", "A3", "A5", "A7", "A9", "A9", "A4", "A6"]
* -----------------------------------------------------------
* compare: A7 A8
* result : -1
* ["A0", "A1", "A2", "A3", "A5", "A7", "A8", "A9", "A4", "A6"]
* -----------------------------------------------------------
* compare: A9 A4
* result : 1
* ["A0", "A1", "A2", "A3", "A5", "A7", "A8", "A9", "A9", "A6"]
* -----------------------------------------------------------
* compare: A8 A4
* result : 1
* ["A0", "A1", "A2", "A3", "A5", "A7", "A8", "A8", "A9", "A6"]
* -----------------------------------------------------------
* compare: A7 A4
* result : 1
* ["A0", "A1", "A2", "A3", "A5", "A7", "A7", "A8", "A9", "A6"]
* -----------------------------------------------------------
* compare: A5 A4
* result : 1
* ["A0", "A1", "A2", "A3", "A5", "A5", "A7", "A8", "A9", "A6"]
* -----------------------------------------------------------
* compare: A3 A4
* result : -1
* ["A0", "A1", "A2", "A3", "A4", "A5", "A7", "A8", "A9", "A6"]
* -----------------------------------------------------------
* compare: A9 A6
* result : 1
* ["A0", "A1", "A2", "A3", "A4", "A5", "A7", "A8", "A9", "A9"]
* -----------------------------------------------------------
* compare: A8 A6
* result : 1
* ["A0", "A1", "A2", "A3", "A4", "A5", "A7", "A8", "A8", "A9"]
* -----------------------------------------------------------
* compare: A7 A6
* result : 1
* ["A0", "A1", "A2", "A3", "A4", "A5", "A7", "A7", "A8", "A9"]
* -----------------------------------------------------------
* compare: A5 A6
* result : -1
* ["A0", "A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8", "A9"]
*
*/
经过上面的执行日志分析，我们发现：javascript中的.sort(sortby)方法使用的是一个冒泡排序的变种方式，当遇到需要调整顺序的相邻元素时，冒泡排序会直接调换两者的位置，但javascript中的.sort(sortby)方法，会将需要前移的元素使用二分法直接插入到正确的位置。
.sort() 方法深层探究[2]: 为什么返回 true/false 对长度为10以内的数组的排序结果不会造成影响
首先，咱们先来分析一下，为什么返回true/false在某些情况下对排序结果没有影响：
根据.sort()函数定义
- 若 a < b，在排序后的数组中 a 应该出现在 b 之前，则返回一个小于 0 的值 （此时不需要调整顺序）。
- 若 a == b，则返回 0 （此时不需要调整顺序）。
- 若 a > b，则返回一个大于 0 的值 （此时需要调整顺序）。
我们可以看出来：只有a > b时，才需要对数组元素调整顺序，而a > b时若按照true/false的返回值来说，应该返回true，而true在javascript中，大家都知道，是等价于1的，是一个大于0的值。正好与函数的定义相匹配，这也说明了为什么在某些情况下，sortby函数即使返回true/false也不会影响排序结果的正确性。
OK，上面也说的，在某些情况下，那么到底在什么情况下呢？
根据我多次测试，在数组长度 <= 10 的情况下，无论返回
true/false还是1/0/-1都不影响排序结果的正确性；而一旦数组长度超过10，排序结果就无法保证了。
为什么是10？
按理说，根据上面的算法分析，我们已经知道了.sort(sortby)函数的具体实现，本来我真的是打算研究一下这个问题的，可是，you know，对于一个算法学渣来说，这个问题还是太难了。。。(﹁"﹁)
权且记录一下，如果哪天我突然顿悟了，我会补回来的٩(ŏ﹏ŏ、)۶
还有，真的，如果哪位大神明白的，麻烦再评论里教我下，感激不尽。。。