javascript - JavaScript "sort()"函数的算法

Question

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

<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() on an array 将使用字符串对数组进行排序。也将整数转换为字符串。呸!

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

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

不管你的数组是否由“字符串数字”组成"5"或者只是数字 5使用您自己的函数对数字进行排序时。因为当 JavaScript 在做数学运算时，它把“字符串数字”当作数字来对待。即 "5" - "3" = 2

排序字符串

当您对字符串进行排序时，您可以使用 > 来比较它们和 < (大于和小于)运算符。大于运算符按升序 (A-Z, 1-9) 对字符串进行排序，小于运算符按降序 (Z-A, 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...):function(a, b){return a > b? 1: -1;}
按降序(Z、Y、X...):function(a, b){return b > a? 1: -1;}

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