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

IT技术 javascript sorting comparator
2021-01-22 03:28:04

以下代码如何按数字顺序对这个数组进行排序?

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”排序为比“b”低的索引:7, 41

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

请帮助一个挣扎的新手!

6个回答

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

是的

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

您可以通过以下方式了解自己:

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
请记住,这是一个类似 wiki 的网站,我们可以编辑其他答案以使其更好:)
2021-03-16 03:28:04
如果排序函数返回 -ve 然后它交换和 +ve 那么它不交换 ??
2021-03-20 03:28:04
@ShekharReddy 您仍然可以使用运算符进行比较。我已经更新了答案。
2021-03-23 03:28:04
而是对 firebug 或 html DIV 元素的 .innerHTML += "comparing " + a + ", " + b + "\n" 执行 console.log;
2021-03-26 03:28:04
只是对新 ES6 语法的说明:array.sort((a,b) => a - b);is valid syntax
2021-04-08 03:28:04

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

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

有许多常用的排序算法,因为没有一种算法是适合所有目的的。最常用于通用排序的两个是Quicksortmerge sort快速排序通常是两者中较快的,但归并排序有一些不错的特性,可以使其成为更好的整体选择。合并排序是稳定的,而快速排序则不是。这两种算法都是可并行化的,但归并排序的工作方式使并行实现更高效,其他一切都相同。

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

ECMAScript 标准现在需要稳定性
2021-03-19 03:28:04
JavaScriptCore 实际上使用 AVL 树进行排序,因为在面对修改正在排序的数组的比较器函数时,它必须具有确定性的行为。
2021-03-27 03:28:04
FWIW,基本的快速排序是一种可以被“欺骗”而表现不佳的算法。在简单的形式中,它对于已经排序或完全颠倒的列表具有 O(N^2) 性能。大多数库快速排序算法都有许多非显而易见的优化,有助于避免这些常见的最坏情况。
2021-04-02 03:28:04

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

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

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

是的,就是这样。回调用于根据需要比较数组中的元素对,以确定它们的顺序。在处理数字排序时,比较函数的这种实现并不是非典型的。规范其他一些更具可读性的网站上的详细信息

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

由于这是一个比较排序,给定 N 个项目,回调函数应该平均调用 (N * Lg N) 次以进行快速排序,例如Quicksort如果使用的算法类似于冒泡排序,则回调函数将被平均调用 (N * N) 次。

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