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

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

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


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

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

小于0 : “ a”被排序为比“ b”更低的索引。
0: “ a”和“ b”被认为是相等的，不执行排序。
大于0: “ b”被排序为小于“ a”的索引。 < br/>

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

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

25(a)-8(b) = 17(大于零，因此排序“ b”的索引值要低于“ a”) : 8,25

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

然后这两组数字是如何相互排序的？

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

48913 次浏览
小开

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

没错，就是这样。回调用于根据需要比较数组中的元素对，以确定元素的顺序。在处理数值排序时，比较函数的实现并不是非典型的。详情在 说明书或在 一些其他 更易读站点。

小开

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

一些排序算法在已经排序的列表上表现不佳，因为它们比典型情况下做了更多的比较。其他人能够很好地处理预先排序的列表，但在其他情况下，他们可能会被“骗”到表现不佳。

目前常用的排序算法有很多，因为没有一种算法是完美的。最常用于泛型排序的两个是 快速排序和 合并排序。快速排序通常是两者中速度较快的，但合并排序有一些很好的属性，可以使它成为一个更好的整体选择。合并排序是 稳定，而 Quicksort 不是。两种算法都是可并行的，但是合并排序的工作方式使得并行实现更加有效，其他条件相同。

您的特定 JavaScript 解释器可能会使用其中一种算法或完全不同的算法。符合 ECMAScript标准的实现必须使用 没有指定哪个算法。它甚至明确否认稳定的必要性。

小开
最佳答案

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

是的

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

你可以通过以下方式找到自我:

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
小开

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

JavaScript 的 sort 需要记住的一点是，它不一定是稳定的。

小开

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

由于这是一种比较排序，因此对于 快速排序这样的快速排序，应该平均(N * Lg N)调用回调函数。如果使用的算法类似于 泡泡排序，那么将平均(N * N)次调用回调函数。

比较排序的最小调用次数是(N-1) ，这仅用于检测已经排序的列表(例如，如果没有发生交换，则在 Bubble Sort 中提前排除)。

小开

深度知识

如果结果为负，则在 b 之前排序。

如果结果为正，则在。

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

小开

为了帮助阐明 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)。

在同样的意义上，我有自由改变我的排序实现，只要我不违反我的规范，ECMAScript 的实现可以自由选择在 语言规范语言规范的范围内的排序实现，所以 Array#sort可能会在不同的引擎上产生不同的比较器调用。如果逻辑依赖于某些特定的比较序列，则不会编写代码(首先，比较器也不应该产生副作用)。

例如，V8引擎(在编写本文时)在数组大于预先计算的元素数时调用 Timsort，并对小数组块使用 二进制插入排序二进制插入排序。然而，它过去使用的 快速排序是不稳定的，可能会给出不同的参数序列和对比较器的调用。

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

小开

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

是的

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

a: 用于比较的第一个元素。

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

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

然后这两组数字是如何相互排序的？

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

大于0: 在 b 之后排序 a

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


提交答案