JavaScript高级函数之排序sort

引入

排序算法作为各学校算法入门的必修课程，一定给各位留下过深刻的印象。不论是经典的冒泡排序、选择排序，还是当今最高效的快速排序，亦或者是比较有趣的栈排序、桶排序，都凝聚了前人过人的智慧和创造力。

不过随着高级语言的出现，似乎当今使用来看我们并不需要每次都自己手码排序算法。像python语言，内置的sorted函数和sort方法允许使用者直接调用来给选定序列排序，并且内部是用c语言基于快速排序编写的，运行效率和占用情况都大大高于我们手码排序算法。

JS也是这样一门高级语言，其带有sort函数可以直接给指定序列排序

今天就让我们一起了解一下js的sort有什么有趣的地方吧——

1. sort方法调用

前面我们介绍过js中“方法”的概念。本质上是和对象建立关联的函数。sort函数默认和array对象建立了关联。所有的array可以直接调用sort方法来进行排序。我们看看效果——

['juejin', 'aliyun', 'cnds'].sort(); // 输出结果为 ['aliyun', 'cnds', 'juejin']

对字符串的排序是从第一个开始一个个字符比对ASCII码来实现的。a<c<j，所以我们自然就得到了如上的输出结果。如果出现首个字符相同，则比较第二个……以此类推

但要注意，大小写字符的ASCII码是不一样的（如果一样的话电脑怎么区分大小写呢？）所以可能会出现下面的情况——

['Juejin', 'aliyun', 'cnds'].sort(); // 输出结果为 [ 'Juejin','aliyun', 'cnds']

如上结果。J是大写字母，大写字母的ASCII码要在小写之前，因而排在最后的j换成大写J了以后直接排在了最前面。

那么针对数值的排序是怎么样的呢？我们来实践一下

[101, 208, 105, 2000].sort(); // [101, 105, 2000, 208]

结果不是我们想要的数值排序。而仍然是字符串排序结果。说明在js中，sort会自动把所有元素转化成字符串类型，再按照字符串的比较方式进行排序

2. sort的自定义排序

那么我们要实现数值的排序应该怎么办呢？这时候就要引入我们的sort函数自定义功能了。

我们可以在sort()中传入一个自定义函数，构造规则一般如下：

设置两个参数，一般为x,y

用分支语句进行条件判断

如果不符合预期排序前后顺序的则return 1，符合预期顺序的return -1，相等时return 0。

举个具体的例子吧。如果我们希望按照数值排序，则可以采用如下代码构造函数

var arr = [101, 208, 105, 2000];
arr.sort(function (x, y) {
    if (x < y) {
        return -1;
    }
    if (x > y) {
        return 1;
    }
    return 0;
}); // [101, 105, 208, 2000]

设置function之后sort便不会直接把array的所有元素转为字符串，而是直接针对函数里的规则进行判断。

在这里我们发现，如果x<y，这说明了小的在前面，符合了我们的预期，于是return -1。x>y是大的数在前面，不符合预期，我们返回1。

其余情况为相等，我们返回0(其实不设置这个也可以，因为相等的数不需要改变顺序。但为了考虑xy相等的情况，如果我们舍弃了return 0，最好把等号放到条件判断里，如把x<y改成x<=y或者把x>y改成x>=y)

在这里不设置return 0并没有任何影响：

我们发现输出值是正确的。

那么请问，倒序的时候应该如何设置呢？

其实很简单，只要把“预期顺序”改变就行，之前我们希望x，y这种顺序是x<y时出现的，所以在x<y的时候return了-1，而现在我们改变了预期，便要让x<y的时候return 1。x>y的情况亦然。修改代码后如下：

arrr = [10, 20, 10, 1, 2, 20, 20, 26, 80]
arrr.sort(function (x, y) {
    if (x <= y) {
        return 1;
    }
    if (x > y) {
        return -1;
    }
});
console.log(arrr);

输出正常。

3. 关于sort的一点思考

很多人一看到这个x,y相比较，就感觉像是冒泡排序

其实这样理解是不对的，冒泡是效率非常低的，业内不会设计由冒泡来作为排序函数的底层逻辑

事实上，js的sort底层原理是由引擎实现的，可能有涉及timsort、快排等多种排序算法。我们作为js使用者、前端工程师而非算法设计师不必细究。有兴趣可以作为拓展知识了解。

此外，关于-1和1，其实在实际使用中可以直接用任意负数、正数替代。这样一来，对数值的排序可以简化成：

arrr = [10, 20, 10, 1, 2, 20, 20, 26, 80]
arrr.sort(function (x, y) {
    return x-y
});
console.log(arrr); 

当x<y的时候，x-y<0,负数，表示符合预期（x小y大，x,y这种x在前y在后的顺序是正确的）。

反之x>y, x-y>0, 正数，不符合预期，因为此时x,y这种大在前小在后的顺序是不应该出现的。

x==y的时候相减为0，0本身也不会影响排序先后，可以忽略。

这就构造了一个升序sort：

输出正常

还有关于我上面提到的“符合预期”理解法，其实是经过我个人简化后的理解。按照主流理解逻辑，function中x和y的关系应该是这样理解的，个人感觉逻辑上需要绕一绕

sort本身只会升序排序，即从小到大。但什么算小，什么算大是可以由我们决定的。

我们只需要举两个数作为例子，告诉计算机什么情况算小，什么情况算大即可

这个“告诉”的规则是，如果对传入的x,y而言，x<y则返回-1，x>y返回1，x==y返回0.

对于数字而言，我们传入的xy分别代表一个数，如果是升序，则符合默认sort逻辑，无需改动。

但如果是降序，我们需要改变计算机认为的大小逻辑，此时x>y时需要让计算机认为是x<y。

举个例子，我们传入的一串数是2，3，1，希望升序排序。sort会的就是升序，于是我们按照我们的逻辑告诉计算机当x比y小时，你要当作x比y小（比如正常逻辑是1小于3，你就让计算机当作1小于3）。计算机sort升序之后就是1，2，3

当我们传入2，3，1，希望降序排序。但是sort只知道升序啊，那我们要实现降序，就得告诉计算机：当x<y的时候，你要当作x>y呀（比如正常逻辑是1小于3，但你告诉计算机1大于3），于是计算机按照他的“新逻辑”升序排序之后，排出来的结果对我们正常逻辑就是降序的。排出来就是3，2，1

这个“新逻辑”不光可以运用在数上，你可以建立任何的“新逻辑”，比较经典的是我们可以忽略大小写判断字符串大小：

var arr = ['Juejin', 'aliyun', 'cnds'];
arr.sort(function (x, y) {
    x1 = x.toUpperCase();
    y1 = y.toUpperCase();
    if (x1 < y1) {
        return -1;
    }
    if (x1 > y1) {
        return 1;
    }
    return 0;
}); // 输出结果为['aliyun', 'cnds', 'Juejin']

我们相当于告诉了计算机，当x1<y1的时候（也就是所有元素都转化成大写的x和y），我们告诉电脑要此时x和y的关系要当作x<y。反之同理。这就完成了一次对字符不区分大小写的升序。

略有冗长，如果一下子有点难理解，不妨还是用简便理解法。但既然想体验coding之美，不如还是尝试着自己想想吧