JavaScript中的sort函数和compare函数是如何工作的？

Question

已经被问过了：JavaScript中的sort函数以及compare函数是如何工作的呢？ 如果我有一个数组，并且执行array.sort(compare)，现在书上写道如果compare函数返回a-b（数组的两个索引值），则排序是基于结果是否大于0、小于0或等于0来完成的。但是，它究竟是如何工作的呢？我无法理解。

- Kraken

---

你需要了解什么？我相当确定所使用的排序算法是特定于实现的。 - ThiefMaster

比较函数与排序的功能有什么关系？它不只是比较两个变量并返回这两个变量的结果吗？整个数组是如何排序的？ - Kraken

可能是Javascript的sort()方法如何工作？的重复问题。 - Bergi

Answer 1

"compare"函数需要接受两个参数，通常称为a和b。然后，根据这些值a和b，使compare函数返回0、大于0或小于0。

1. 如果a大于b，则返回大于0的值。
2. 如果a等于b，则返回0。
3. 如果a小于b，则返回小于0的值。

通过这三种返回值，且只有两个参数，可以编写一个比较函数来排序任何类型的输入数据类型或复杂数据结构。

然后，在调用sort()函数时，使用您自定义的compare函数，该函数将在待排序列表中的一对元素上调用，以确定适当的顺序。

让我们通过一个简单的示例来解释... 假设您只对一些数字进行排序，因此我们有一个非常简单的compare函数：

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()函数，因此可以对任意复杂的数据进行排序，而不仅仅是数字。

- Jonathan Hall

---

以上情况下的时间复杂度如何？ - thisizkp

每个函数都有时间复杂度。我很确定JavaScript的.sort()使用快速排序（n log n），但是通过调用次要函数compare(a,b)，会增加多少时间复杂度呢？我认为由于比较是线性的，所以该函数仍然保持渐近行为。如果有人可以确认这一点，那就太好了！ - David Sánchez

那么，我们是不是应该在排序之前自己声明比较函数，否则sort()方法怎么知道我们使用的是哪个比较函数呢？ - GLPease

@FadeocKhaos 当你执行number.sort(a, b)（如上例所示），你将比较函数作为参数传递给sort()。在JavaScript数组中，sort()接受比较函数作为可选参数。由于在这种情况下，比较函数只充当引用，因此它充当匿名函数。这本身是一个更广泛的主题，但我希望这可以帮助你。如果单独发布问题，我可以为您提供详细信息。谢谢。 - rock

@ranjith 谢谢，这很有帮助。 - GLPease

Answer 2

默认情况下，数组的sort()方法按字母升序排序。如果您想以其他方式对数组进行排序，因为数组包含数字或对象，则可以将一个函数传递给sort()。

您传递的函数接受两个参数，通常称为a和b，并返回： 如果第一个参数应该在第二个参数之前排序（a<b），则返回负数 如果参数相等（a==b），则返回0 如果第一个参数应该在第二个参数之后排序（a>b），则返回正数

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

对于数字，您的函数可以具有if / else if / else结构来决定返回什么结果，但是简单地返回（a-b）就可以为您实现这一点，因为减法的结果将为-ve，0或+ve，并正确地按升序放置数字。返回（b-a）会使它们降序。

  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结构。

对于您正在排序具有多个属性的对象的示例，您可以进一步扩展它以包括二次排序，也就是说（在我的示例中），如果名称属性相等，那么您可以返回比较，例如，电话属性。

- nnnnnn

---

我更喜欢这个答案，因为它包括了一个带有字符串比较的例子 +1。 - Klik

我喜欢“sort()将被重复调用”的描述。+1 - Buddybear

那么，当排序数字时，我可以返回-1、0、1，或者我可以返回b - a或a - b。结果是一样的，对吗？在这种情况下，-1和1没有什么特别的区别或显著差异吗？ - CodeFinity

@VisWebsoft - 是的，结果将会是一样的。 - nnnnnn

Answer 3

该方法使用Array.sort的语法和参数顺序（compareFunction和sortOptions），其参数定义如下：

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

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

- gamgam

---

参考链接：https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array/sort - fullStackChris

Answer 4

我们可以简化正序排序和倒序排序。

第一个参数是a。

第二个参数是b。

function compare(a, b) {
  //  make some operations to calculate these variables as true or false
  //     weNeedToMoveFirstParameterInPositiveDirection
  //     weDoNotNeedToMove
  //     weNeedToMoveFirstParameterInNegativeDirection

  // just think about numerical axis <------(-1)---(0)---(1)------>
  if (weNeedToMoveFirstParameterInPositiveDirection) return 1;  
  if (weDoNotNeedToMove) return 0; 
  if (weNeedToMoveFirstParameterInNegativeDirection) return -1;  
}

- mustafa kemal tuna

---

为什么人们没有对此发表多少评论？这很好记住比较器结果将如何影响结果。 - Rohit

同意Rohit的观点，这是一个聪明而有帮助的解释。 - Robin Zimmermann

Answer 5

如果数组是字符串类型的，排序方法会把数字作为字符串处理，这时候不需要比较函数。 但是如果数组是数字类型的，你需要使用比较函数来改变排序方法的行为。

例1：字符串类型的数组

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

示例2：数字

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

- Eiko No Shance

Answer 6

目前可以使用 Uint32Array 创建数组。

[https://istack.dev59.com/qBgvm.webp]

但是，它存在一些困难。例如，您无法向数组添加新值。简单地说，您无法修改数组的长度。

- Nicolas Mellado

Answer 7

我认为可能是这样的（好吧，我不确定）：

假设函数compare(a,b)是比较函数。 它返回c。 假设我们要对数组N中的条目进行排序，以获得排序结果数组M。

我不知道确切的排序算法，而且如果c既不是(a-b)也不是(b-a)（例如，如果c是"b-2"、"a+b"或其他一些表达式），不同的浏览器甚至会返回不同的结果。

但根据ECMA-262，排序结果应该是这样的：

a，b可以是任意两个索引。 这意味着我们实际上向比较函数传递了一个有序对。 例如：(0,1),(1,4)，甚至是(2,0)，(2,1)。

ECMAScript语言规范指出，结果应具有以下属性： (a,b)是传递给比较函数的有序对。

• 如果函数返回的 c 小于零，则必须满足 M(a)< M(b)。

而规范并没有说明如果 c 等于零或大于零会发生什么。

我不确定这是否正确。 至少这可以很容易地解释为什么当 c 是 "a-b" 时，条目按数字和升序排序，而当 c 是 "b-a" 时，条目按相反顺序排序。

浏览器的 js 引擎是否真的严格按照 `ECMA-262` 设计，还是我完全错了？

参考：

ECMA-262 第五版（请查看第129-130页）

- fececagec812

Answer 8

排序实际上与比较函数关系不大，从某种意义上说，它并不类似于算法，而更像是算法的输出结果。

---

模型与示例

1. 取数组 [1,4,3,5],
2. 首先在心中对其进行排序（部分排序）：[1, 3,...]，按照你希望的排序方式。

这可能是棘手的一部分：

3. 从你心中排序好的数组中选取一对元素：
   • 左边的元素为b，右边的元素为a

现在根据这个模型定义compareFn。

示例1

(不使用三元运算符)

const myArray = [1,4,3,5]

function compareFn(a,b){
   if(b < a) return 1
   return -1
}

console.log(myArray.sort(compareFn))

例子2

const myArray = [1,4,3,5]

function compareFn(a,b){
   return b > a ? 1 : -1
}

console.log(myArray.sort(compareFn))

---

（你可以反转第3步的想法，还有排序函数。）

- user12582392