面试官:手写一个 JavaScript 的 Array.sort 方法


我们先来分析一下 JavaScript 的 Array.sort() 方法的功能特性。

Array.sort 详解

在JavaScript中,Array 对象的 sort() 方法是用来排序的,但是这个方法在默认情况下可能不是我们想要的,比如对于如下数组

var arr = [2,5,10,20,7,15];

使用sort排序会得到如下结果:[10, 15, 2, 20, 5, 7],在不传递参数的情况下,它是按字符的 Unicode 编码来排序的。

为了解决这个问题,可以为 sort() 方法传递一个参数,这个参数 ECMAScript 是这么定义的:

/**
@param {function} [compareFn]
@return {Array.<T>}
*/
Array.prototype.sort = function(compareFn) {};

参数为一个 function,具体叫比较函数。我们可以改写为如下形式,传递一个比较函数:

arr.sort(function(a,b){
    return a - b;
});

a 和 b 即是要比较的两个数,其返回值如下:

  • 若 a 小于 b,在排序后的数组中 a 应该出现在 b 之前,则返回一个小于 0 的值。
  • 若 a 等于 b,则返回 0。
  • 若 a 大于 b,则返回一个大于 0 的值。

对于返回值的三种结果,我们可以直接使用 a-b,这样就可以正确得到结果 [2, 5, 7, 10, 15, 20]

手写实现 Array.sort

那么,接下来我们就来模拟一下这个方法和比较函数的实现。

首先,如果我们不用这个方法,而是自己实现排序,那么我们可以使用传统的冒泡排序方法:

function sort(array){
    for(var i=0; i<array.length - 1; i++){
        // 假设数组已经排好序了
        var isSorted = true;
        for(var j=0; j<array.length - 1 - i; j++){
            if(array[j] > array[j + 1]){
                var temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                // 还有比较,说明排序还未结束
                isSorted = false;
            }
        }
        // 如果排序已经完成,跳出循环
        if(isSorted){
            break;
        }
    }
}

这是一个循环次数最少的排序方法,但是,这个排序的适应性不强,对于字符串数组就不行了,假设有如下字符串数组,要求按字符串个数排序该如何实现?

var arry = ["aaa","aa","c","bb"."xxxxxxxx"];

这样的数组我们不得不重新写一个方法来对字符串数组进行排序,需要改动上面冒泡排序的第6行的判断条件:

if(array[j].length > array[j+1].length){}

既然只需要改动这一句,我们可以把这一句作为参数传递,以后想怎么排就传什么样的参数,这个参数就是一个函数,回调函数。下面重新改写上面的冒泡排序,传递一个回调函数。

// 模拟sort()
function sort(array,fn){
    for(var i=0; i<array.length - 1; i++){
        var isSorted = true;
        for(var j=0; j<array.length - 1 - i; j++){
            if(fn(array[j], array[j + 1]) > 0){
                var temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                    isSorted = false;
                }
            }
        }
        if(isSorted){
           break;
        }
    }
}

注意第 2 行和第 6 行,给 sort 传递了一个 fn 参数,这是一个函数,然后在第 6 行调用,array[j]array[j+1] 分别就是回调函数的 a,b 两个比较值。用这个改写的方法即可对数值数组排序也可以对字符串数组排序了。

var arr = ["aaa","a","xxxxxx","abcd","ab"];
sort(arr, function (a,b) {
    return a.length - b.length;
});
console.log(arr);

输出:[“a”, “ab”, “aaa”, “abcd”, “xxxxxx”]。

全文完,你学会了吗?


文章作者: 张张
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 张张 !
 上一篇
如何正确高效的使用群聊? 如何正确高效的使用群聊?
完全没用过 WeChat 或扣扣群聊的人恐怕很少。我们工作和日常交流中,难免要借助于 WeChat 或是扣扣群的形式进行沟通。
2017-02-13
下一篇 
零碎笔记:移动Web特别样式处理 零碎笔记:移动Web特别样式处理
高清图片问题高清图片跟我们平时下的那种电影高清图片是不一样的,移动Web的高清图片的概念是我这张图这么大,清晰度这么多,那么我们在移动设备上就该展示这么清晰。那么为什么会产生模糊呢?假如一张图片 100px * 100px 那我们在移动设备
2016-10-10
  目录