如何正确地对整数数组进行排序

Question

尝试从一个我知道只包含整数的数组中获取最高和最低值似乎比我想象的更难。

var numArray = [140000, 104, 99];
numArray = numArray.sort();
console.log(numArray)

我希望它展示的是99, 104, 140000，但实际上它展示的是104, 140000, 99。因此看起来排序函数将这些值视为字符串。

有没有办法让排序函数按照整数值进行排序？

- peirix

---

顺便说一下，如果你要排序大量的整数，最好使用类似于计数排序这样的整数排序算法。计数排序所需运行的时间与数组大小成线性关系：O(n)。而本文中提供的所有解决方案都使用比较排序，效率较低：O(n * log n)。 - Web_Designer

计数排序在考虑数字范围时是线性的，而不是考虑数组大小。例如，对于[1,1000000]进行排序需要超过2步，因为算法必须扫描1到1000000之间的每个数组索引，以查看哪个单元格的值大于0。 - yters

JS仍然存在这个bug，这相当疯狂。 - user894319twitter

@user894319twitter说："这太不真实了，我真的只能称之为一个 bug。如果这在规范中，那么他们在规范中指定了一个 bug。这是一个 bug。" - gjvdkamp

我真的很想知道是什么思维过程导致了这个结论：“这是sort()的一个很好的实现”。 - Welcor

Answer 1

默认情况下，sort方法按字母顺序排序元素。要按数字排序，只需添加一个处理数字排序的新方法（如下所示sortNumber）-

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

var numArray = [140000, 104, 99];
numArray.sort(function(a, b) {
  return a - b;
});

console.log(numArray);

文档:

在不包含Infinity或NaN的数组中，Mozilla Array.prototype.sort() 推荐使用此比较函数。(因为 Infinity - Infinity 不是0，而是 NaN)。

还有按键排序对象的示例。

- aks

---

好的。但是是否真的没有一种现成的方法可以从Javascript中得到数字排序？ - peirix

啊哈，这是非常新颖的做法！但如果你真的很不切实际，你可以在 JavaScript 刚开始时将函数绑定到数组类上：// Array.prototype.sortNormal = function(){return this.sort(function(a,b){return a - b})} // 现在，在任何数组上调用 .sortNormal() 都会按数字大小排序。 - Jack Franzen

为什么用 a-b 而不是 a>b。我建议使用后者以避免操作机器错误。 - Luca Davanzo

比较函数应该返回-1、0或+1，而a>b将只返回true或false。 - Iván Pérez

这段代码可以使用箭头函数来缩短。numberArray.sort((a, b) => (a - b)); 太好了！我认为这很接近开箱即用的方式。注意：请检查您的JS引擎是否支持箭头函数。 - Константин Ван

Answer 2

继承以上所有答案，它们也可以像这样在一行中完成：

var numArray = [140000, 104, 99];
numArray = numArray.sort(function (a, b) {  return a - b;  });

//outputs: 99, 104, 140000

- MarzSocks

---

我认为你的意思是在一个表达式中完成。 - maxjvh

修正后：var arr = [140000, 104, 99].sort(function(a,b) { return a-b; });或者更简洁的ES6写法：let arr = [140000, 104, 99].sort((a,b) => a-b); - 00500005

Answer 3

我很惊讶为什么每个人都推荐给sort()传递一个比较函数，这会使排序变慢。

要对数字进行排序，只需创建任意的TypedArray：

var numArray = new Float64Array([140000, 104, 99]);
numArray = numArray.sort();
console.log(numArray)

- dy_

---

使用 TypedArray 可以将排序速度提高约 5 倍。如果您想要更快的速度，hpc-algorithms npm 包实现了基数排序和计数排序，这里有几个答案建议使用它们。 - DragonSpit

@Nikolay D，那些是未签名的。您可以使用Int32Array。 - rion18

@Gio 不确定那是正确的。内存需求仅为O(2n)，对于一个包含一百万项的数组来说只有几兆字节。至于速度——将数组转换为类型化数组、排序并再次转换回来，仍然比使用函数对数组进行排序要快。 - dy_

使用自定义排序函数sort((a, b) => a - b)非常快。只有在处理大型数组时，使用Typed Array才有好处，它不支持动态大小或推送，并且实例化一个也比[]花费更多时间，因此这完全取决于用途。我会说，如果您处理的元素数组少于20k，请不要使用typed arrays。 - Pawel

有趣的是，这里有一群人在讨论性能，却没有提供可运行的基准测试(a)，也没有说明他们使用的浏览器/引擎/操作系统/处理器(b)，也没有提供任何经过测量的时间数据（平均多次运行，并进行零假设检验）(c)。 - Jonas Wilms

Answer 4

array.sort默认使用词典排序，如果需要进行数字排序，请提供自己的函数。以下是一个简单的示例：

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

numArray.sort(compareNumbers);

还要注意，sort方法会直接在原对象上进行排序，不需要进行赋值操作。

- Paul Dixon

---

我不理解上面的代码，"return a - b" 如何进行升序排序？ - vikramvi

如果a < b，compareNumbers返回一个负数。如果a > b，则返回正数。如果相等，则返回0。 - Paul Dixon

因为它只会返回 true 或 false，而比较函数需要返回一个负数、零或者正数。 - Paul Dixon

Answer 5

这个答案和现有的一些答案等价，但是ECMAScript 6的箭头函数提供了一种更加紧凑的语法，可以定义一个内联排序函数而不损失可读性：

numArray = numArray.sort((a, b) => a - b);

今天大多数浏览器都支持箭头函数（详情）

- jjjjs

Answer 6

只需使用.sort((a, b) => a - b)而不是.sort()本身。此外，该数组会在原地排序，因此返回值并不重要。

var numArray = [140000, 104, 99];
numArray.sort((a, b) => a - b);
console.log(numArray)

- norbekoff

---

非常有帮助！ - parsecer

Answer 7

排序函数表现奇怪的原因

来自文档：

根据每个字符的Unicode代码点值，按照每个元素的字符串转换对数组进行排序。

如果打印数组的Unicode代码点值，则问题将变得清晰。

console.log("140000".charCodeAt(0));
console.log("104".charCodeAt(0));
console.log("99".charCodeAt(0));

//Note that we only look at the first index of the number "charCodeAt(  0  )"

这将返回："49, 49, 57"。

49 (unicode value of first number at 140000)
49 (unicode value of first number at 104)
57 (unicode value of first number at 99)

现在，因为 140000 和 104 返回了相同的值（49），它会切掉第一个索引并再次检查：

console.log("40000".charCodeAt(0));
console.log("04".charCodeAt(0));

//Note that we only look at the first index of the number "charCodeAt(  0  )"

52 (unicode value of first number at 40000)
40 (unicode value of first number at 04)

如果我们对此进行排序，那么我们将得到：

40 (unicode value of first number at 04)
52 (unicode value of first number at 40000)

所以104比140000先出现。

So the final result will be:

var numArray = [140000, 104, 99];
numArray = numArray.sort();
console.log(numArray)

104, 140000, 99

结论:

sort()只根据数字的第一位进行排序，不关心整个数字的大小，它比较数字中每个字符的unicode值大小，如果两个unicode值相等，则会检查下一个数字并进行比较。

要正确排序，您必须像这里所解释的那样传递一个比较函数给sort()。

- Black

---

提示：这只是我的解释，我并没有真正查看代码。因此，请不要完全信任这个答案。 - Black

Answer 8

升序 (Ascending)

arr.sort((a, b) => a - b);

降序排列

arr.sort((a, b) => b - a);

只是为了好玩：

降序 = 升序 + 反转

arr.sort((a, b) => a - b).reverse();

- R.M. Reza

Answer 9

Array.sort 默认使用字母排序而不是数字排序。

为了支持数字，可以像下面一样添加：

var numArray = [140000, 104, 99];
numArray.sort((a, b) =>  a - b); // <-- Ascending
numArray.sort((a, b) =>  b - a); // <-- Descending
console.log(numArray);

输出：

- Sangwin Gawande

Answer 10

我同意aks的观点，不过我们可以改用

return a - b;

你应该使用

return a > b ? 1 : a < b ? -1 : 0;

- user3587638

---

为什么有人要使用您读起来更困难的三元运算符？据我所知，它会产生相同的结果。 - stefannew

此答案也考虑了相等的值，并将它们保留在原来的位置。 - Maarten00

对于这个问题（针对javascript，且所有输入项都是整数），"return a-b"可能足够了，但我个人更喜欢三元形式，因为它更规范 -- 它可以在更多情况下、更多的编程语言中、处理更多数据类型。例如，在C语言中，a-b可能会溢出，导致排序无尽循环、损坏存储器、崩溃等等。话虽如此，即使使用三元形式，如果涉及到NaN或混合类型，也无法正常工作。 - Don Hatch

> 和 < 仍将 a 和 b 视为字符串进行比较。 - vriesdemichael

有一种情况下，这个答案能够对于某些 a - b 无法正确评估的数字返回正确的结果。当 a = b = -Infinity 时，a - b = NaN，但是三元运算符返回了 0。但是这似乎并不影响排序，它仍然可以完美地实现。 (a > b) - (a < b) 是一个更短的版本，与这个三元运算符等价。 - Artyer