JavaScript“sort()”函数的算法

Algorithm of JavaScript "sort()" Function

提问by Knowledge Craving

Recently when I was working with JavaScript "sort()" function, I found in one of the tutorialsthat this function does not sort the numbers properly. Instead to sort numbers, a function must be added that compares numbers, like the following code:-

最近，当我使用 JavaScript 的“sort()”函数时，我在其中一个教程中发现该函数不能正确地对数字进行排序。为了对数字进行排序，必须添加一个比较数字的函数，如下面的代码：-

<script type="text/javascript">
function sortNumber(a,b)
{
    return a - b;
}

var n = ["10", "5", "40", "25", "100", "1"];
document.write(n.sort(sortNumber));
</script>

The output then comes as:-

然后输出如下：-

1,5,10,25,40,100

Now what I didn't understand is that why is this occurring & can anybody please tell in details as to what type of algorithm is being used in this "sort()" function? This is because for any other language, I didn't find this problem where the function didn't sort the numberscorrectly.

现在我不明白的是为什么会发生这种情况，任何人都可以详细说明在这个“ sort()”函数中使用的是什么类型的算法？这是因为对于任何其他语言，我没有发现函数没有正确排序数字的问题。

Any help is greatly appreciated.

任何帮助是极大的赞赏。

采纳答案by Justin Ethier

Well, if you are sorting the following list, it contains only strings:

好吧，如果您对以下列表进行排序，则它仅包含字符串：

var n = ["10", "5", "40", "25", "100", "1"];

So I would expect anylanguage would compare them as strings, thus resulting in a sort order of:

所以我希望任何语言都会将它们作为字符串进行比较，从而导致排序顺序：

var n = ["1", "10", "100", "25", "40", "5"];

Which necessitates your code to use a custom sort (as you have done) to cast the strings back to integers for the purposes of sorting.

这需要您的代码使用自定义排序（正如您所做的那样）将字符串转换回整数以进行排序。

Edit

编辑

As Pointy mentioned, by default the JavaScript sort() methodsorts elements alphabetically, including numbers:

正如 Pointy 所提到的，默认情况下，JavaScript sort() 方法按字母顺序对元素进行排序，包括数字：

By default, the sort() method sorts the elements alphabetically and ascending. However, numbers will not be sorted correctly (40 comes before 5). To sort numbers, you must add a function that compare numbers.

默认情况下， sort() 方法按字母顺序和升序对元素进行排序。但是，数字将无法正确排序（40 在 5 之前）。要对数字进行排序，您必须添加一个比较数字的函数。

Simply amazing... so a custom sort is required even for an array of integers.

简直太神奇了……所以即使是整数数组也需要自定义排序。

回答by Aust

To answer your question on how the sorting function works, I will explain it in detail. As has been said in most of the answers here, calling only sort()on an array will sort your array using strings. Converting your integers to strings as well. Blech!

为了回答您关于排序功能如何工作的问题，我将详细解释。正如此处的大多数答案中所说，仅调用sort()数组将使用字符串对数组进行排序。也将您的整数转换为字符串。布莱克！

If you think of your items as characters instead of numbers it makes sense that it would be sorted that way. A good way to see this is to assign letters to your numbers.

如果您将项目视为字符而不是数字，那么按这种方式排序是有道理的。看到这一点的一个好方法是为您的数字分配字母。

//0 = a
//1 = b
//2 = c
//4 = e
//5 = f
//These two arrays are treated the same because they're composed of strings.
var nums  = ["10", "5", "40", "25", "100", "1"];
var chars = ["ba", "f", "ea", "cf", "baa", "b"];

//Here we can see that sort() correctly sorted these strings. Looking at the
//alphabetical characters we see that they are in the correct order. Looking
//at our numbers in the same light, it makes sense that they are sorted
//this way as well. After all, we did pass them as strings to our array.
chars.sort(); //["b", "ba", "baa", "cf", "ea", "f"]
nums.sort();  //["1", "10", "100", "25", "40", "5"]

//The bad part of sort() comes in when our array is actually made up of numbers.
var nums = [10, 5, 40, 25, 100, 1];
nums.sort(); //[1, 10, 100, 25, 40, 5]

//As a result of the default sorting function converting numbers to strings 
//before sorting, we get an unwanted result. We can fix this by passing in our 
//own function as a parameter to sort().

You can control how to sort the array by passing your own function as a parameter to the sort()function. This is nice, but unless you know how the sort()function works, it really won't do you any good.

您可以通过将您自己的函数作为参数传递给函数来控制如何对数组进行排序sort()。这很好，但除非你知道这个sort()函数是如何工作的，否则它真的对你没有任何好处。

sort()will call your function multiple times to re-arrange the array. Depending on what is returned from your function tells sort()what to do with the items in the array. If a negative number or 0 is returned, no re-arranging happens. If a positive number is returned, the two items switch place. sort()keeps track of which numbers it has already tested, so it doesn't end up testing numbers again later after it has switched the items around. If sort()re-arranges items, it will move back one position and see if it has tested these two items before. If it hasn't it will test them. If it has, it will continue on without running your function on them.

sort()将多次调用您的函数以重新排列数组。根据您的函数返回的内容，告诉sort()如何处理数组中的项目。如果返回负数或 0，则不会发生重新排列。如果返回正数，则两个项目交换位置。sort()跟踪它已经测试过的数字，所以它不会在切换项目后再次测试数字。如果sort()重新排列项目，它会向后移动一个位置，看看它之前是否测试过这两个项目。如果没有，它将测试它们。如果有，它将继续运行而不在它们上运行您的函数。

Sorting Numbers

排序数字

Let's take a simple example and I will walk you through it:

让我们举一个简单的例子，我将引导您完成它：

var arr = [50, 90, 1, 10, 2];

arr = arr.sort(function(current, next){
    //My comments get generated from here
    return current - next;
});

//1 : current = 50, next = 90
//  : current - next (50 - 90 = -40)
//  : Negative number means no re-arranging
//  : Array now looks like [50, 90, 1, 10, 2]
//
//2 : current = 90, next = 1
//  : current - next (90 - 1 = 89)
//  : Positive number means sort() will switch these positions in the array
//  : Array now looks like [50, 1, 90, 10, 2]
//
//If sort() didn't backtrack, the next check would be 90 and 10, switch those 
//positions, check 90 and 2, and switch again. Making the final array
//[50, 1, 10, 2, 90], not sorted. But lucky for us, sort() does backtrack.
//
//3 : current = 50, next = 1
//  : current - next (50 - 1 = 49)
//  : Positive number means sort() will switch these positions in the array
//  : Array now looks like [1, 50, 90, 10, 2]
//
//If sort() wasn't smart, it would now check 50 and 90 again. What a waste! 
//But lucky for us again, sort() is smart and knows it already made this 
//check and will continue on.
//
//4 : current = 90, next = 10
//  : current - next (90 - 10 = 80)
//  : Positive number means sort() will switch these positions in the array
//  : Array now looks like [1, 50, 10, 90, 2]
//
//sort() backtracks one position and sees that it has not checked 50 and 10
//
//5 : current = 50, next = 10
//  : current - next (50 - 10 = 40)
//  : Positive number means sort() will switch these positions in the array
//  : Array now looks like [1, 10, 50, 90, 2]
//
//sort() backtracks one position and sees that it has not checked 1 and 10
//
//6 : current = 1, next = 10
//  : current - next (1 - 10 = -9)
//  : Negative number means no re-arranging
//  : Array now looks like [1, 10, 50, 90, 2]
//
//sort() remembers that it already checked 10 and 50 so it skips ahead
//sort() remembers that it already checked 50 and 90 so it skips ahead
//
//7 : current = 90, next = 2
//  : current - next (90 - 2 = 88)
//  : Positive number means sort() will switch these positions in the array
//  : Array now looks like [1, 10, 50, 2, 90]
//
//sort() backtracks one position and sees that it has not checked 50 and 2
//
//8 : current = 50, next = 2
//  : current - next (50 - 2 = 48)
//  : Positive number means sort() will switch these positions in the array
//  : Array now looks like [1, 10, 2, 50, 90]
//
//sort() backtracks one position and sees that it has not checked 10 and 2
//
//9 : current = 10, next = 2
//  : current - next (10 - 2 = 8)
//  : Positive number means sort() will switch these positions in the array
//  : Array now looks like [1, 2, 10, 50, 90]
//
//sort() backtracks one position and sees that it has not checked 1 and 2
//
//10: current = 1, next = 2
//  : current - next (1 - 2 = -1)
//  : Negative number means no re-arranging
//  : Array now looks like [1, 2, 10, 50, 90]
//
//sort() remembers that it already checked 2 and 10 so it skips ahead
//sort() remembers that it already checked 10 and 50 so it skips ahead
//sort() remembers that it already checked 50 and 90 so it skips ahead
//sort() has no more items to check so it returns the final array
//which is [1, 2, 10, 50, 90]

If you wanted the array to be ordered in descending order [90, 50, 10, 2, 1]you can just change the return statement from return current - next;to return next - current;like so:

如果您希望数组按降序排列，[90, 50, 10, 2, 1]您只需将 return 语句从 更改return current - next;为return next - current;如下所示：

var arr = [50, 90, 1, 10, 2];

arr = arr.sort(function(current, next){
    //My comments get generated from here
    return next - current;
});

//1 : current = 50, next = 90
//  : next - current (90 - 50 = 40)
//  : Positive number means sort() will switch these positions in the array
//  : Array now looks like [90, 50, 1, 10, 2]
//
//2 : current = 50, next = 1
//  : next - current (1 - 50 = -49)
//  : Negative number means no re-arranging
//  : Array now looks like [90, 50, 1, 10, 2]
//
//etc.

It does not matter if your array is composed of "string numbers" "5"or just numbers 5when using your own function to sort numbers. Because when JavaScript is doing math, it treats "string numbers" as numbers. i.e. "5" - "3" = 2

在使用您自己的函数对数字进行排序时，您的数组是由“字符串数字”组成"5"还是仅由数字组成并不重要5。因为当 JavaScript 进行数学运算时，它将“字符串数字”视为数字。IE"5" - "3" = 2

Sorting Strings

排序字符串

When you sort strings, you can compare them using the >and <(greater-than and less-than) operators. The greater-than operator sorts the string by ascending order (A-Z, 1-9), and the less-than operator sorts by descending order (Z-A, 9-1). Different browsers use different sorting algorithms so when sorting by strings you have to make sure you are returning either 1 or -1, not true or false.

对字符串进行排序时，可以使用>和<（大于和小于）运算符进行比较。大于运算符按升序 (AZ, 1-9) 对字符串进行排序，小于运算符按降序 (ZA, 9-1) 对字符串进行排序。不同的浏览器使用不同的排序算法，因此在按字符串排序时，您必须确保返回 1 或 -1，而不是 true 或 false。

For example, this works in Chrome and FF, but not IE:

例如，这适用于 Chrome 和 FF，但不适用于 IE：

var arr = ['banana', 'orange', 'apple', 'grape'];

arr = arr.sort(function(current, next){
    return current > next;
});

The way to make sure your sorting algorithm works in every browser, use the ternary operator.

确保您的排序算法适用于每个浏览器的方法是使用三元运算符。

var arr = ['banana', 'orange', 'apple', 'grape'];

arr = arr.sort(function(current, next){
    return current > next? 1: -1;
});

When changing the way you're sorting (by ascending or descending order), in addition to changing the operators, you could keep the same operator and switch the currentand nextvariables as we did when sorting numbers. Or since we are using the ternary operator, you could switch the 1and -1.

当改变你的排序方式（升序或降序）时，除了改变运算符之外，你可以保持相同的运算符并切换current和next变量，就像我们在对数字进行排序时所做的那样。或者因为我们使用的是三元运算符，您可以切换1and -1。

Sorting Objects

排序对象

Here is a neat trick that I thought I'd add in here. You can sort objects if you add them to an array and use their key to compare. Here is an example.

这是一个巧妙的技巧，我想我会在这里添加。如果将对象添加到数组并使用它们的键进行比较，则可以对对象进行排序。这是一个例子。

var arr = [
    {id: 2, name: 'Paul'},
    {id: 1, name: 'Pete'}
];

//sort numerically
arr = arr.sort(function(current, next){
    return current.id - next.id;
});
//Array now looks like [{id: 1, name: 'Pete'}, {id: 2, name: 'Paul'}]

//sort alphabetically
arr = arr.sort(function(current, next){
    return current.name > next.name? 1: -1;
});
//Array now looks like [{id: 2, name: 'Paul'}, {id: 1, name: 'Pete'}]

Recap

回顾

To sort numbers
in ascending order (1, 2, 3...): function(a, b){return a - b;}
in descending order (9, 8, 7...): function(a, b){return b - a;}

要按升序 (1, 2, 3...)对数字
进行排序： 按降序 (9, 8, 7...)：function(a, b){return a - b;}
function(a, b){return b - a;}

To sort strings
in ascending order (A, B, C...): function(a, b){return a > b? 1: -1;}
in descending order (Z, Y, X...): function(a, b){return b > a? 1: -1;}

按升序对字符串
进行排序 (A, B, C...):function(a, b){return a > b? 1: -1;}
按降序 (Z, Y, X...)：function(a, b){return b > a? 1: -1;}

To sort objectsadd them to an array,
then sort by key: function(a, b){return a.key - b.key;}

要对对象进行排序，请将它们添加到数组中，
然后按键排序：function(a, b){return a.key - b.key;}

回答by Daniel Wedlund

Javascript's sort sorts by default lexicographical, alphabetical. Thus as I understand it every element is treated as a string. The internal sorting algorithm is most probably quicksort or mergesort. To be able to use quicksort you need to be able to relate elements to each other, is a bigger than b? In the string case this ordering is already implemented.

Javascript 的排序默认按字典顺序、字母顺序排序。因此，据我所知，每个元素都被视为一个字符串。内部排序算法很可能是快速排序或归并排序。为了能够使用快速排序，您需要能够将元素相互关联，a 是否大于 b？在字符串情况下，这种排序已经实现。

Since you might want to sort your custom datatypes etc. you can provide a functional defining how to order two elements.

由于您可能想要对自定义数据类型等进行排序，因此您可以提供一个定义如何对两个元素进行排序的函数。

From your example your functional determines the order of two numbers a and b. Javascript sort then uses your function telling sort how to order the elements.

从您的示例中，您的功能确定了两个数字 a 和 b 的顺序。Javascript sort 然后使用您的函数告诉 sort 如何对元素进行排序。

Turns out that mergesort is used by Mozilla, look at: Javascript Array.sort implementation?

原来Mozilla使用了mergesort，看：Javascript Array.sort implementation？

回答by Giuseppe Accaputo

The function sortwill sort your array in an alphabetical sort order, even if it consists of integers; that's the reason why your array is sorted like that by calling sortwithout a parameter.

该函数sort将按字母排序顺序对您的数组进行排序，即使它由整数组成；这就是为什么通过sort不带参数调用来对数组进行排序的原因。

sortOrderis a comparison function that is used to define a new sort order for the array; this function will return

sortOrder是一个比较函数，用于为数组定义新的排序顺序；这个函数会返回

• 0, if aand bare of the same value
• a value > 0, if ahas a bigger value than b
• a value < 0, if ahas a smaller value than b

• 0, 如果a和b具有相同的值
• 一个值> 0，如果a值大于b
• 一个值< 0，如果a值小于b

In JavaScript, "1" - "2"will return -1, which is a number, and not a string anymore; by using the comparison function sortOrderon your array consisting of numbers wrapped in strings, you're ordering the array in a numerical sort order, thus resulting in 1,5,10,25,40,100, and not in 1,10,100,25,40,5

在 JavaScript 中，"1" - "2"将返回-1一个数字，不再是字符串；通过sortOrder对包含在字符串中的数字组成的数组使用比较函数，您按数字排序顺序对数组进行排序，从而导致1,5,10,25,40,100，而不是1,10,100,25,40,5

回答by Michael Borgwardt

The problem lies with the use of strings to represent numbers, which the sort function unfortunately does as default. Strings are sorted alphabetically. The comparison function in your code just forces the strings to be evaluated as numbers.

问题在于使用字符串来表示数字，不幸的是 sort 函数默认这样做。字符串按字母顺序排序。代码中的比较函数只是强制将字符串计算为数字。

I'd consider it very bad API design that the sort function defaults to treating the elements as strings, but it may be necessary given JavaScript's loose type system..

我认为排序函数默认将元素视为字符串是非常糟糕的 API 设计，但鉴于 JavaScript 的松散类型系统，这可能是必要的。

回答by KooiInc

You can delegate the sorting to your own sort function:

您可以将排序委托给您自己的排序函数：

function sortnum(a,b) {
 return parseInt(a,10)-parseInt(b,10);
}
var n = ["10", "5", "40", "25", "100", "1"];
alert(n.sort(sortnum)); //=>["1", "5", "10", "25", "40", "100"]

回答by Mark Baker

And what if your n is defined as:

如果您的 n 定义为：

var n = [10, 5, 40, 25, 100, 1]; 

回答by ihorbond

The “default” comparison function calls toString on both values and does a lexicographical comparison on the string representations. V8 engine uses Timsort algorithms which runs in O(nlogn). Source

“默认”比较函数对两个值调用 toString 并对字符串表示进行字典序比较。V8 引擎使用以 O(nlogn) 运行的 Timsort 算法。 来源