JavaScript"sort()"函数的算法

Question

最近,当我使用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>

然后输出如下: -

1,5,10,25,40,100

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

任何帮助是极大的赞赏.

Answer 1

要回答关于排序功能如何工作的问题,我将详细解释.正如在这里的大多数答案中所说的,仅调用sort()数组将使用字符串对数组进行排序.将整数转换为字符串.布莱什!

如果您将项目视为字符而不是数字,则可以按照这种方式进行排序.看到这个的好方法是为你的数字分配字母.

//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().

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

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

排序数字

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

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]

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

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.

如果您的数组由"字符串数字"组成,"5"或者5在使用您自己的函数对数字进行排序时只是数字,则无关紧要.因为当JavaScript进行数学运算时,它会将"字符串数字"视为数字.即"5" - "3" = 2

排序字符串

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

例如,这适用于Chrome和FF,但不适用于IE:

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

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

确保排序算法在每个浏览器中都有效的方法,使用三元运算符.

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

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

在更改排序方式时(按升序或降序排列),除了更改运算符之外,还可以保留相同的运算符并切换current和next排序数字时的变量.或者因为我们使用三元运算符,您可以切换1和-1.

排序对象

这是一个巧妙的技巧,我认为我会在这里添加.如果将对象添加到数组并使用其键进行比较,则可以对对象进行排序.这是一个例子.

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'}]

概括

排序号码
在升序(1,2,3,...) :function(a, b){return a - b;}
在降序(9,8,7 ...) :function(a, b){return b - a;}

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

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

Answer 2

好吧,如果你要对以下列表进行排序,它只包含字符串:

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

所以我希望任何语言都将它们作为字符串进行比较,从而产生以下排序顺序:

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

这需要您的代码使用自定义排序(如您所做)将字符串强制转换为整数以进行排序.

编辑

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

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

简直太棒了......所以即使对于一个整数数组也需要自定义排序.

Answer 3

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

由于您可能希望对自定义数据类型等进行排序,因此可以提供定义如何对两个元素进行排序的功能.

从您的示例中,您的函数确定两个数字a和b的顺序.Javascript sort然后使用你的函数告诉排序如何排序元素.

原来,Mozilla使用mergesort,看看:Javascript Array.sort实现？

Answer 4

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

我认为非常糟糕的API设计,sort函数默认将元素视为字符串,但在给定JavaScript的松散类型系统时可能是必要的.

Answer 5

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

sortOrder是一个比较函数,用于定义数组的新排序顺序; 这个功能会回来

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

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