Javascript的sort()方法是如何工作的?

137

以下代码如何将数组按数字顺序排序?

var array=[25, 8, 7, 41]

array.sort(function(a,b){
  return a - b
})

我知道如果计算结果小于0,"a"会按顺序排在"b"之前。
如果计算结果等于0,"a"和"b"被认为是相等的,不进行排序。
如果计算结果大于0,"b"会按顺序排在"a"之前。

在排序过程中,排序回调函数会被调用多次吗?

如果是这样的话,我想知道每次传递给函数的是哪两个数字。我最初认为第一次传入的是"25"(a)和"8"(b),接着是"7"(a)和"41"(b),因此:

25(a) - 8(b) = 17 (大于0,所以按顺序排序"b"应该在"a"之前): 8, 25

7(a) - 41(b) = -34 (小于0,所以按顺序排序"a"应该在"b"之前:7, 41

那么这两组数字是如何相对排序的呢?

请帮助一个苦苦挣扎的新手!

8个回答

72

数组排序回调函数在排序过程中被调用多次吗?

是的。

如果是这样,我想知道每次传递给函数的两个数字是哪两个。

你可以使用以下方法自己找出:

array.sort((a,b) => {
  console.log(`comparing ${a},${b}`);
  return a > b ? 1
               : a === b ? 0 
                         : -1;
});

编辑

这是我得到的输出:

25,8
25,7
8,7
25,41

8
最好用 console.log 打印到 Firebug 或者 html 的 DIV 元素的 .innerHTML += "comparing " + a + ", " + b + "\n"。 - Joshua
3
请记住,这是一个类似维基百科的网站,我们可以编辑其他人的答案使它们更好 :) - Pablo Fernandez
10
ES6新语法提示:array.sort((a,b) => a - b); 是有效的语法。 - Sterling Archer
1
如果排序函数返回负数,则进行交换,如果返回正数,则不进行交换吗? - Mahi
如果数组是字符串数组怎么办?我无法理解其中发生了什么。 - Shekhar Reddy
2
@ShekharReddy 你仍然可以使用运算符进行比较。我已经更新了答案。 - OscarRyz

55
JavaScript解释器内置了某种排序算法实现。在排序操作期间,它会调用比较函数多次。比较函数被调用的次数取决于特定算法、要排序的数据以及排序之前的顺序。
一些排序算法在已经排序好的列表上表现不佳,因为它们会比通常情况下进行更多的比较。其他算法对预排序列表有良好的处理能力,但在其他情况下可能会被"欺骗"而表现不佳。
由于没有单一的算法适用于所有目的,因此有许多常用的排序算法。用于通用排序的两个最常用的算法是快速排序归并排序。快速排序通常比归并排序更快,但归并排序具有一些良好的属性,可以使它成为更好的选择。归并排序是稳定的,而快速排序则不是。这两种算法都可以并行化,但归并排序的工作方式使得并行实现更加高效,其他条件相同。
你的 JavaScript 解释器可能会使用其中一种算法或者完全不同的算法。ECMAScript 标准 没有指定实现必须使用哪种算法。它甚至明确否认了稳定性的需求。

1
就算是基本的快速排序算法也有可能被“欺骗”而表现不佳。在简单形式下,对于已经排序或完全相反的列表,其性能为O(N^2)。大多数库中的快速排序算法都有许多非显而易见的优化,可以避免这些常见的最坏情况。 - Adisak
3
JavaScriptCore实际上使用AVL树进行排序,因为在比较器函数修改待排序数组的情况下,需要表现出确定性。 - olliej
3
ECMAScript标准现在要求稳定性。 - ggorlen

14

深入了解

如果结果为负数,则a在b之前排序。

如果结果为正数,则b在a之前排序。

如果结果为0,则不对两个值的排序顺序进行更改。

注意:

此代码是按步骤查看排序方法中的视图。

输出:

let arr = [90, 1, 20, 14, 3, 55];
var sortRes = [];
var copy = arr.slice();  //create duplicate array
var inc = 0; //inc meant increment
copy.sort((a, b) => {
 sortRes[inc] = [ a, b, a-b ];
 inc += 1;
 return a - b;
});
var p = 0;
for (var i = 0; i < inc; i++) {
 copy = arr.slice();
 copy.sort((a, b) => {
  p += 1;
  if (p <= i ) {
   return a - b;
  }
  else{
   return false;
  }
 });
 p = 0;
 console.log(copy +' \t a: '+ sortRes[i][0] +' \tb: '+ sortRes[i][1] +'\tTotal: '+ sortRes[i][2]);
}


13

一次比较一个值对,这些值对是逐一比较的。比较的值对是实现细节--不要假设它们在每个浏览器上都相同。回调函数可以是任何东西(所以你可以对字符串或罗马数字等任何东西进行排序,只要你能想出一个返回1、0、-1的函数)。

需要记住的一件事是 JavaScript 的 sort() 函数不能保证稳定性。


9
为了更好地解释Array#sort及其比较器的行为,考虑一下在初级编程课程中教授的这个天真的插入排序

const sort = arr => {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j && arr[j-1] > arr[j]; j--) {
      [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
    }
  }
};

const array = [3, 0, 4, 5, 2, 2, 2, 1, 2, 2, 0];
sort(array);
console.log("" + array);

忽略插入排序算法的选择,关注硬编码比较器:arr[j-1] > arr[j]。这个比较器有两个与讨论相关的问题:
  1. > 运算符在一对数组元素上被调用,但是你可能想要排序的许多东西(例如对象)不能以合理的方式响应 > (如果我们使用 - 也是如此)。
  2. 即使你正在处理数字,通常你想要的是除了升序排序之外的其他排列方式。

我们可以通过添加一个你熟悉的 comparefn 参数来解决这些问题:

const sort = (arr, comparefn) => {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j && comparefn(arr[j-1], arr[j]) > 0; j--) {
      [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
    }
  }
};

const array = [3, 0, 4, 5, 2, 2, 2, 1, 2, 2, 0];
sort(array, (a, b) => a - b);
console.log("" + array);

sort(array, (a, b) => b - a);
console.log("" + array);

const objArray = [{id: "c"}, {id: "a"}, {id: "d"}, {id: "b"}];
sort(objArray, (a, b) => a.id.localeCompare(b.id));
console.log(JSON.stringify(objArray, null, 2));

现在,简单排序例程已经被泛化。您可以准确地看到此回调函数何时被调用,从而回答您的第一组问题:
“在排序过程中,数组排序回调函数是否会被多次调用?如果是这样,我想知道每次传递给函数的两个数字是哪两个。”
运行下面的代码将显示,是的,该函数被多次调用,并且您可以使用console.log查看传入的数字:

const sort = (arr, comparefn) => {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j && comparefn(arr[j-1], arr[j]) > 0; j--) {
      [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
    }
  }
};

console.log("on our version:");
const array = [3, 0, 4, 5];
sort(array, (a, b) => console.log(a, b) || (a - b));
console.log("" + array);

console.log("on the builtin:");
console.log("" + 
  [3, 0, 4, 5].sort((a, b) => console.log(a, b) || (a - b))
);

你问:

那么这两组数字是如何相互排序的?

确切地说,ab不是数字的集合,它们是数组中的对象(在您的示例中,它们是数字)。

事实上,排序的方式并不重要,因为它取决于实现。如果我使用的排序算法与插入排序不同,比较器可能会对不同的数字对进行调用,但在排序调用结束时,对于JS程序员而言,重要的不变式是结果数组根据比较器排序,假设比较器返回符合您所述的契约的值(当a < b时小于0,当a === b时等于0,当a > b时大于0)。

在同样的意义上,只要不违反规范,我有自由更改我的排序实现方式,ECMAScript 的实现也可以在 语言规范 的限制范围内自由选择排序实现方式,所以 Array#sort 在不同引擎上可能会产生不同的比较器调用。一个人不应编写依赖于某个特定比较顺序的逻辑代码(比较器本身也不应该产生副作用)。
例如,V8引擎(撰写时)在数组大于某个预先计算的元素数量时调用Timsort,并对小型数组块使用二进制插入排序。然而,它曾经使用不稳定的quicksort,可能会给比较器带来不同的参数序列和调用。
由于不同的排序实现以不同的方式使用比较器函数的返回值,当比较器不遵守合同时,这可能会导致令人惊讶的行为。请参见此线程的示例。

6

在排序过程中,数组的回调函数会被多次调用吗?

是的,正是这样。在必要时,回调函数用于比较数组中的元素对,以确定它们应该排列的顺序。当处理数字排序时,实现比较函数并不罕见。有关详细信息,请参阅规范或其他一些更易读的网站


5

在排序期间,数组排序回调函数会被调用多次吗?

由于这是一种比较排序算法,对于N个项目,像快速排序这样的快速排序平均应该调用(N * Lg N)次回调函数。如果使用的算法类似于冒泡排序,则回调函数将平均调用(N * N)次。

比较排序的最小调用次数为(N-1),仅用于检测已排序列表(即,在冒泡排序中提前退出,如果没有发生交换)。


0
数组排序回调函数在排序过程中会被调用多次吗?
是的
如果是这样,我想知道每次传递给函数的两个数字是哪两个。
a:用于比较的第一个元素。
b:用于比较的第二个元素。
在以下示例中,a将在第一次迭代中为“2”,b将为“3”
那么这两组数字如何相对排序?
元素根据比较函数的返回值进行排序。
大于0:在b之后排序a
小于0:在b之前排序a
等于0:保持a和b的原始顺序
这里有一个例子

var arr = [3, 2, 1, 5, 4, 6, 7, 9, 8, 10];
console.log(arr.sort((a, b) => {
  console.log(a - b, a, b);
  //b-a if sorting in decending order
  return a - b; 
}));


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接