javascript - 为什么 compareFunction 必须考虑负值？

Question

Array.prototype.sort()

在compareFunction(a, b)中，只有当我们需要交换a和b的位置时，我们才返回一个正值。

如果省略compareFunction中的否定if-statement，Array.prototype.sort()仍然有效，那么开发人员为什么要写if 语句 返回负值？

var list = [4, 5, 3, 5, 6, 9, 1, 4, 2];
list = list.sort(function(a, b) {
  if (a > b) {
    return 1;
  }
});
console.log(list); // correct result

Answer 1

这里的主要问题是您发明了自己的比较函数定义，并以此为基础提出您的问题:

In compareFunction(a, b), only when we need to exchange a and b's position, we return a positive value.

这是不正确的。 “当我们需要交换 a 和 b 的位置时”是一个实现细节，您将实现与接口(interface)混淆了。

compareFunction 不负责指示何时应交换两个元素。它负责准确传达两个元素之间的关系。排序算法如何处理该信息取决于实现者。如果您只是在某些时候返回正确的值，那么您不能一直期望得到正确的结果。

例如，排序实现者可以像这样实现排序(基于 https://www.nczonline.net/blog/2012/09/17/computer-science-in-javascript-insertion-sort/ 中的示例)。如果我使用有效的比较函数运行它，它会产生正确的结果:

function insertionSort(items, compare) {

  var len = items.length, // number of items in the array
    value, // the value currently being compared
    i, // index into unsorted section
    j; // index into sorted section

  for (i = 0; i < len; i++) {

    // store the current value because it may shift later
    value = items[i];

    for (j = i - 1; j > -1 && compare(value, items[j]) < 0; j--) {
      items[j + 1] = items[j];
    }

    items[j + 1] = value;
  }

  return items;
}

console.log(insertionSort([4,2,6,1,7,2], (l, r) => l - r));

如果我用你的比较函数运行它，它什么都不做:

function insertionSort(items, compare) {

  var len = items.length, // number of items in the array
    value, // the value currently being compared
    i, // index into unsorted section
    j; // index into sorted section

  for (i = 0; i < len; i++) {

    // store the current value because it may shift later
    value = items[i];

    for (j = i - 1; j > -1 && compare(value, items[j]) < 0; j--) {
      items[j + 1] = items[j];
    }

    items[j + 1] = value;
  }

  return items;
}

console.log(insertionSort([4,2,6,1,7,2], function(a, b) {
    if (a > b) {
        return 1;
    }
}));