排序函数如何在 JavaScript 中与比较函数一起工作

IT技术 javascript
2021-01-21 03:12:25

正如已经问过的:排序函数如何在 JavaScript 中与compare函数一起工作?如果我有一个数组,我array.sort(compare)现在这样,书中写道,如果compare函数返回a-b(数组的两个索引),那么它的工作原理是结果是大于 0、小于 0 还是等于0. 但是,它究竟是如何工作的?我无法解决。

6个回答

“比较”函数必须采用两个参数,通常称为ab然后根据这些值ab使比较函数返回 0、大于 0 或小于 0

  1. 如果a大于b,则返回大于 0
  2. 如果a等于b,则返回 0
  3. 如果a小于b,则返回小于 0

有了这三个返回值和两个参数,就可以编写一个比较函数,它可以对任何类型的输入数据类型或复杂的数据结构进行排序。

然后,当您使用自定义比较函数调用 sort() 时,将在待排序列表中的对上调用比较函数,以确定正确的顺序。

让我们来看一个简单的例子......假设你只对一些数字进行排序,所以我们有一个非常简单的比较函数:

function compare(a,b) {
    return a - b;
}

如果 a 大于 b,则简单地从 a 中减去 b 将始终返回大于零,如果它们相等,则返回 0,如果 a 小于 b,则返回小于零。因此它满足比较功能的要求。

现在让我们假设这是我们要排序的数字列表:

var numbers = [1,5,3.14];

当您调用 时numbers.sort(compare),它会内部实际执行:

compare(1,5);     // Returns -4, a is less than b
compare(1,3.14);  // Return -2.14, a is less than b
compare(5,3.14);  // returns 1.86, a is greater than b

如果您曾经进行过手动排序或按字母顺序排列,那么您已经完成了完全相同的事情,但可能没有意识到这一点。即使您可能有数十或数百个项目要比较,但您一次只能比较两个数字(或作者的姓氏,或其他)。再次浏览或列出三个数字,您首先要比较前两个数字:

  1. 1是大于还是小于5?小于,所以把这两个数字放在我们的列表中:1,5
  2. 3.14 是大于还是小于 1?大于,所以它在新列表中的 1 之后
  3. 3.14 在我们的新列表中是大于还是小于 5?小于,所以它在 5 之前。我们的新列表现在是 [1,3.14,5]

因为您可以提供自己的 compare() 函数,所以可以对任意复杂的数据进行排序,而不仅仅是数字。

上述情况下的时间复杂度如何?
2021-03-14 03:12:25
@FadeocKhaos 当您执行 number.sort(a, b) (如上例所示)时,您将比较函数作为参数传递给 sort()。JavaScript 数组中的 sort() 接受比较 fn 作为可选参数。由于在这种情况下比较 fn 仅充当参考,因此它充当匿名函数。这本身就是一个更广泛的话题,但我希望这会有所帮助。如果作为单独的问题发布,我可以为您提供有关此的详细信息。谢谢。
2021-03-14 03:12:25
@ranjith 谢谢你,它有帮助。
2021-03-19 03:12:25
每个函数都有时间复杂度。我很确定 javascript .sort() 使用快速排序 (n log n ),但他通过调用辅助函数 compare(a,b) 询问将添加多少。我会说由于比较是线性的,所以函数仍然保持渐近行为。如果有人能证实这一点,那就太好了!
2021-04-03 03:12:25
那么,我们应该在排序之前自己声明比较函数,否则 sort() 方法如何知道我们正在使用哪个比较函数?
2021-04-05 03:12:25

默认情况下,数组sort()方法按字母升序排序。如果您想以其他顺序排序,因为您的数组包含数字或对象,那么您可以将函数传递给sort().

您传入的函数接受两个参数,通常称为 a 和 b,并返回: 如果第一个参数应该排在第二个之前,则为负数 (a < b) 0 如果参数相等 (a==b) 正数如果第一个参数应该在第二个 (a > b) 之后排序,则为 number

现在,这里是关键点:您作为参数传递给的函数sort()将在sort()处理整个数组时重复调用sort()不知道或不关心数组中事物的数据类型:每次需要知道“项目 A 是否在项目 B 之前?” 它只是调用你的函数。您无需担心 内部使用哪种类型的排序算法sort(),实际上一个浏览器可能使用与另一个浏览器不同的算法,但这没关系,因为您只需要提供一种方法来比较数组中的任意两个项目.

你的函数可以有一个if / else if / else结构来决定返回什么结果,但对于数字,简单地返回 (ab) 将为你实现这一点,因为减法的结果将是 -ve、0 或 +ve,并且正确地将数字按升序排列。返回 (ba) 会使它们降序:

  var sortedArray = myArray.sort(function(a,b){
                                    return (a-b);
                                });

如果您有一个对象数组并且想要对对象的某个或多个特定属性进行排序,您也可以这样做。假设,例如,这种格式的对象:

{ id : 1,
  name : "Fred",
  address : "12 Smith St",
  phone : "0262626262" }

然后,您可以按其 'id' 属性对此类对象的数组进行排序,如下所示:

var sortedArray = myArray.sort(function(a,b){
                                  return (a.id - b.id);
                              });

或者,您可以按“名称”属性(字母顺序)对此类对象的数组进行排序,如下所示:

var sortedArray = myArray.sort(function(a,b){
                                   if (a.name < b.name)
                                      return -1;
                                   else if (a.name == b.name)
                                      return 0;
                                   else
                                      return 1;
                               });

请注意,在我的最后一个示例中,我已经放置了if / else if / else之前提到的完整结构。

对于您对具有多个属性的对象进行排序的示例,您可以进一步扩展它以包括二级排序,也就是说,(在我的示例中)如果名称属性相等,则您可以返回一个比较,例如,电话属性。

我喜欢描述“sort() 将被重复调用”+1
2021-03-24 03:12:25
我更喜欢这个答案,因为它包含一个字符串比较 +1 的示例。
2021-04-07 03:12:25
因此,在对数字进行排序时,我可以返回 -1, 0, 1 OR 我可以返回b - aOR a - b结果会一样,是吗?无显著差异或什么特别之处-1,并1在这方面?
2021-04-11 03:12:25
@VisWebsoft - 是的,结果是一样的。
2021-04-11 03:12:25

该方法使用了Array.sort(compareFunction sortOptions)的语法和参数,其参数定义如下:

compareFunction - 一个比较函数,用于确定数组元素的排序顺序。该参数是可选的。应该使用比较函数来比较两个参数。给定元素的 A 和 B,compareFunction 的结果可以是负值、0 或正值:

如果返回值为负,则表示在排序序列中 A 出现在 B 之前。如果返回值为 0,则 A 和 B 具有相同的排序顺序。如果返回值为正,则表示在排序序列中 A 出现在 B 之后。

sort 方法单独将数字视为字符串,因此如果字符串数组不需要比较函数。但是如果数字数组需要比较函数来改变排序方法的构建行为。

ex1:字符串

var animals = ["Horse", "Cat", "Tiger", "Lion"];  
animals.sort();

ex2 : 数字

var marks = [70, 90, 60, 80 ];  
marks.sort(function(a, b){return a > b}); //ascending , a < b descending . 

您现在可以使用 Uint32Array 来创建数组。

[ https://i.stack.imgur.com/qBgvm.png]

但是,它有一些困难。例如,您不能向数组添加新值。简单地说,您不能修改数组长度。