JavaScript中sort方法的一个坑（leetcode 179. Largest Number）

在做 Largest Number 这道题之前，我对 sort 方法的用法是非常自信的。我很清楚不传比较因子的排序会根据元素字典序（字符串的UNICODE码位点）来排，如果要根据大小排序，需要传入一个比较函数。

先来看这道题，给你一个数组，让你把数组元素拼接起来，求能拼得的最大的数。如果只有两个数字 a 和 b，如何拼？很明显比较 ab 和 ba 两个数的大小，所以这道题首先需要对数组做一次排序。刷刷写下如下代码：

nums.sort(function(a, b) {
  return (b + '' + a) > (a + '' + b);
});

因为 ba 和 ab 位数相同，我觉得根据字典序即可比较大小，提交，221 组数据跪在了 201 组。我开始怀疑算法的正确性，直到无意中把比较函数改了下，便 AC 了：

nums.sort(function(a, b) {
  return (b + '' + a) - (a + '' + b);
});

这真的有区别么？印象中 c++ 中调用 STL 的 sort 函数，在比较函数中一直用的 < 以及 > 啊。我承认我以前从没有留意过。

我们把问题简化，先来看以下代码：

var largestNumber = function(nums) {
  nums.sort(function(a, b) {
    return a - b;
  });

  return nums;
};

console.log(largestNumber([41,32,81,97,99,91,90,63,76,76,67]));
// [32, 41, 63, 67, 76, 76, 81, 90, 91, 97, 99]

这是一次升序排序，结果完美，那么，为什么能得到这样的结果，有思考过 return a - b 的意思么？

如果指明了 compareFunction ，那么数组会按照调用该函数的返回值排序。记 a 和 b 是两个将要被比较的元素：

如果 compareFunction(a, b) 小于 0 ，那么 a 会被排列到 b 之前；
如果 compareFunction(a, b) 等于 0 ， a 和 b 的相对位置不变。
如果 compareFunction(a, b) 大于 0 ， b 会被排列到 a 之前。

上面的的代码其实可以扩写成这样：

var largestNumber = function(nums) {
  nums.sort(function(a, b) {
    if (a - b > 0)
      return 1; // a 比 b 大，b 排到 a 前
    else if (a - b < 0)
      return -1;  // a 比 b 小，a 排到 b 前
    else 
      return 0; // a 和 b 一样大，a 和 b 相对位置不变
  });

  return nums;
};

仔细想想，这样便是一个升序排列。

再来看错误写法：

var largestNumber = function(nums) {
  nums.sort(function(a, b) {
    return a > b;
  });

  return nums;
};

console.log(largestNumber([41,32,81,97,99,91,90,63,76,76,67]));
// [91, 41, 32, 63, 67, 76, 76, 81, 90, 97, 99]

其实可以扩写为：

var largestNumber = function(nums) {
  nums.sort(function(a, b) {
    if (a > b)
      return 1; // true 隐式转换为 1; b 排到 a 前
    else 
      return 0; // false 隐式转换为 0; 相对位置不变
  });

  return nums;
};

仔细想想，明显有问题。a > b 时 b 排到 a 前没有问题，a < b 时位置不变，这就不对了。如果 a < b 时 return -1，让 a 排到 b 前，就对了。所以这样写也是没问题的：

var largestNumber = function(nums) {
  nums.sort(function(a, b) {
    if (a > b)
      return 1; 
    else 
      return -1;
  });

  return nums;
};

当然，a === b 这个条件可以随意归到 a > b 或者 a < b 那，也可以拎出来独立，以上代码我是归到 a < b 那了。

另外还需要注意的一点是，比较函数中的 a 和 b 参数，在数组中的位置是任意的，并不是 a 前 b 后。这里我写了段测试代码：

var largestNumber = function(nums) {
  nums.sort(function(a, b) {
    console.log(a, b);
    console.log(nums.concat());
    return a - b;
  });

  return nums;
};

console.log(largestNumber([41,32,81,97,99,91,90,63,76,76,67]));

结果很明显：

最后勉强回忆起 C++ 中的 sort 的比较函数返回的是一个 bool 值，而 JavaScript 比较函数能返回三个值，跟 C++ 中的 qsort 类似？实在回忆不起来也不想回忆了。

本题完整代码可以移步 https://github.com/hanzichi/leetcode/tree/master/Algorithms/Largest Number。PS：还有一个坑，拼起来的字符串需要去前导 0。