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

Array.prototype.sort()

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

如果省略了if-statement中的负compareFunction，则Array.prototype.sort()仍然有效，为什么开发人员应该编写返回负值的if-statement？

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

最佳答案

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


  在compareFunction（a，b）中，仅当我们需要交换a和b的位置时，我们才返回一个正值。


这是不正确的。 “何时需要交换a和b的位置”是一个实现细节，您正在使实现与接口混淆。

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;
    }
}));