前几天看一道面试题，要求根据num对下面的对象倒序排序。
var arr = [
{name:'A',num:4},
{name:'G',num:3},
{name:'V',num:5},
{name:'A',num:2},
{name:'X',num:9},
{name:'R',num:6},
{name:'N',num:undefined},
];
对于对象按照属性排序 MDN-Array.sort() 上有介绍。下面是MDN上的栗子。
var items = [
{ name: 'Edward', value: 21 },
{ name: 'Sharpe', value: 37 },
{ name: 'And', value: 45 },
{ name: 'The', value: -12 },
{ name: 'Magnetic' },
{ name: 'Zeros', value: 37 }
];
items.sort(function (a, b) {
if (a.value > b.value) {
return 1;
}
if (a.value < b.value) {
return -1;
}
// a 必须等于 b
return 0;
});
于是我们可以简单地写出答案：
arr.sort(function(){
return b.num - a.num;
});
我对数组中含有undefined时的排序情况有不小的疑惑。
当num的值全部是正常数字时， arr将会被正常倒序排序，那么在有特殊值的情况下将如何排序呢。这里分别测试了两种情况。
- num的值为undefined
在完成正常数值的倒序排序后，num值为undefined的对象被放到了最后。后来改成正序测试undefined仍然被放到了最后。
- num的值未定义(在这里我将题中的num:undefined直接删去)
不管正序还是倒序，num值未定义的对象依然被扔在最后。
为了查看其排序原理，我们用一个简单的数组模拟一下来看看每一次排序后数组的变化。（正序）
var arr = [4, 3, 5, 2, undefined, 9 ,6 ]; function compare(a, b) { console.log(a, b, arr); return a - b; } arr.sort(compare);
控制台结果：
undefined在第一次排序前就被扔到了后面，但对比一下原数组： [4, 3, 5, 2, undefined, 9 ,6 ] >> [4, 3, 5, 2, 6, 9, undefined]
发现undefined与数组的最后一位做了交换。实际上我们的compare()函数压根没有将undefined列入考虑范围，而是遇到直接扔到数组最后再进行排序。num值未定义的时候也同理。
了解了undefined的情况，我们来看一下正常情况下的排序机制。
第一次： 4大于3，两者交换位置 [3, 4, 5, 2, 6 ,9]，看起来像是运用了冒泡排序。
第二次： 4小于5，没有位置交换 [3, 4, 5, 2, 6 ,9]
第三次： 5大于2，在这里仅仅是5覆盖了2的位置得到 [3, 4, 5, 5, 6, 9]
第四次： 4大于2，4又覆盖了5的位置得到 [3, 4, 4, 5, 6, 9]
第五次： 3大于2，这时2出现得到 [2, 3, 4, 5, 6, 9]
第六次： 5小于6，位置不变，第七次同。
最终得到正序排序结果。
上述的排序过程中只有第一次做了一次交换，再看第三四五次都与2做了比较并且有移位的过程。这与插入排序的过程类似。但是第一次不能确定是用了冒泡还是插入排序。
实际上第一次也同样使用了插入排序。假设确实是冒泡，那么第一次排序会将两两相邻的数一直比较至数列尽头（第二次倒着往前比较）。不能把一次交换就简单认为是冒泡排序。
使用冒泡的第一次排序后顺序应该是 [3, 4, 2, 5, 6, 9].
换一组数再来测验一下 var arr = [4, 3, 1, 2, -1];
可以得出结论sort()函数主要运用了简单插入排序算法。下面是我偷来的图解释了插入排序的动态过程。
注：上面的测试全部在chrome环境下实现，不同的浏览器使用的排序机制可能不同。