Javascript 的 sort() 是如何工作的？

Question

下面的代码如何按数字顺序对该数组进行排序？

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

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

我知道如果计算结果是...

小于 0：“a”被排序为比“b”更低的索引。
零：“a”和“b”被视为相等，并且不执行排序。
大于0：“b”被排序为比“a”更低的索引。

在排序过程中是否多次调用数组排序回调函数？

如果是这样，我想知道每次将哪两个数字传递给函数。我假设它首先需要“25”(a)和“8”(b)，然后是“7”(a)和“41”(b)，所以：

25(a) - 8(b) = 17（大于小于零，因此将“b”排序为低于“a”的索引）： 8, 25

7(a) - 41(b) = -34（小于零，因此将“a”排序为低于“a”的索引） "b": 7, 41

那么两组数字如何相互排序？

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

Answer 1

深度知识

如果结果为负，则 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]);
}

Answer 2

比较成对的值，一次一对。所比较的对是实现细节——不要假设它们在每个浏览器上都是相同的。回调可以是任何内容（因此您可以对字符串或罗马数字或其他任何可以得出返回 1,0,-1 的函数进行排序）。

关于 JavaScript 的排序需要记住的一件事是它不能保证稳定。

Answer 3

帮助阐明 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))
);

你问：

这两组数字如何相互排序？

准确地说，a 和 b 不是数字的集合 - 它们是数组中的对象（在您的示例中，它们是数字）。

事实是，它们如何排序并不重要，因为它依赖于实现。如果我使用与插入排序不同的排序算法，比较器可能会在不同的数字对上调用，但在排序调用结束时，对 JS 程序员来说重要的不变量是结果数组根据比较器，假设比较器返回符合您规定的约定的值（当 a < b 时为 <0，当 a === b 时为 0，当 a === b 时为 > 0 a>b）。

从同样的意义上说，只要我不违反我的规范，我就可以自由地更改排序的实现，ECMAScript 的实现可以在 语言规范，因此 Array#sort 可能会在不同引擎上产生不同的比较器调用。人们不会编写逻辑依赖于某些特定比较序列的代码（比较器也不应该首先产生副作用）。

例如，V8 引擎（在撰写本文时）调用 Timsort 当数组大于预先计算的元素数量并使用 针对小数组块的二进制插入排序。但是，它曾经使用 quicksort ，这是不稳定的，可能会给出不同的参数序列，并且调用比较器。

由于不同的排序实现使用比较器函数的返回值不同，因此当比较器不遵守约定时，这可能会导致令人惊讶的行为。有关示例，请参阅此线程。

Answer 4

数组排序回调函数在排序过程中是否被多次调用？

是的，就是这样。回调用于根据需要比较数组中的元素对，以确定它们应采用的顺序。在处理数字排序时，比较函数的实现并不罕见。详细信息请参阅规范或一些其他更具可读性 的网站。

Answer 5

数组排序回调函数在排序过程中是否被多次调用？

由于这是比较排序，给定 N 个项目，回调函数应平均调用 (N * Lg N) 次，以实现快速排序，如 快速排序。如果使用的算法类似于冒泡排序，那么平均会调用回调函数（ N*N) 次。

比较排序的最小调用次数是 (N-1)，并且仅检测已排序的列表（即，如果没有发生交换，则在冒泡排序中尽早退出）。

Answer 6

数组排序回调函数在排序过程中是否被多次调用？

是的

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

a：要比较的第一个元素。

b：用于比较的第二个元素。

在以下示例中，第一次迭代中 a 将为“2”，b 将为“3”

这两组数字如何相互排序？

元素根据比较函数的返回值进行排序。

大于0：将a排序在b之后

小于0：将a排序在b之前

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

Answer 7

数组排序回调函数在排序过程中是否被多次调用？

是

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

您可以通过以下方式找到自己：

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

Answer 8

JavaScript 解释器内置了某种排序算法实现。它在排序操作期间多次调用比较函数。调用比较函数的次数取决于特定算法、要排序的数据以及排序之前的顺序。

某些排序算法在已排序的列表上表现不佳，因为这会导致它们进行比典型情况更多的比较。其他人可以很好地处理预先排序的列表，但在其他情况下，他们可能会被“欺骗”而表现不佳。

有许多常用的排序算法，因为没有一种算法能够完美地满足所有目的。最常用于通用排序的两个是 Quicksort 和 合并排序。快速排序通常是两者中更快的一个，但合并排序有一些很好的属性，可以使其成为更好的整体选择。归并排序稳定，而快速排序则不然。两种算法都是可并行的，但在其他条件相同的情况下，合并排序的工作方式使并行实现更加高效。

您的特定 JavaScript 解释器可能会使用其中一种算法或完全使用其他算法。 ECMAScript 标准 未指定一致性实现必须使用哪种算法。它甚至明确否认对稳定的需要。