美文网首页基础算法@IT·互联网Web前端之路
Array.prototype.sort()方法到底是如何排序的

Array.prototype.sort()方法到底是如何排序的

作者: 快减肥成功的胖纸 | 来源:发表于2017-05-01 02:25 被阅读124次

    本文除了会带大家了解一些Array.prototypr.sort()方法(后面简写为sort()方法)的基本定义和用法之外,还会探讨一下sort()方法到底是使用的什么排序算法。简单度娘了一下,网上的那些sort()方法详解文章,大多只说了sort()方法的用法。还有说sort()方法是使用冒泡法做的排序,这是错误的。下面,我们发车!

    sort()方法

    先来看看sort()方法的一些基础知识。已经了解sort()方法的童鞋可以直接跳过这部分。

    定义

    sort() 方法在适当的位置对数组的元素进行排序,并返回数组。 sort 排序不一定是稳定的。

    语法

    arr.sort()
    arr.sort(compareFunction)

    说明

    1.如果没有指明 compareFunction ,那么元素会按照转换为的字符串的诸个字符的Unicode位点进行排序。

    2.如果指明了 compareFunction ,那么数组会按照调用该函数的返回值排序。即 a 和 b 是两个将要被比较的元素:
       a.如果 compareFunction(a, b) 小于 0 ,那么 a 会被排列到 b 之前;
       b.如果 compareFunction(a, b) 等于 0 , a 和 b 的相对位置不变。(ECMAScript 标准并不保证这一行为,而且也不是所有浏览器都会遵守,例如 Mozilla 在 2003 年之前的版本);
       c.如果 compareFunction(a, b) 大于 0 , b 会被排列到 a 之前。
      d. compareFunction(a, b)必须总是对相同的输入返回相同的比较结果,否则排序的结果将是不确定的。(利用这一特性,可实现随机排序)

    3.如果数组包含undefined元素(元素值为undefined或元素末定义)

    以上90%引用自MDN

    实例
    //例1.字母排序
    var a = new Array("banna","watermelon","orange","apple");
    s.sort(); 
    console.log(a) //输出 ["apple", "banna", "orange", "watermelon"]
    //没什么好说的,比较函数缺省,按照字母顺序升序排序 a<b<o<w
    
    //例2.转化为字母排序
    var a=[11,2,44,3,5,6];
    a.sort();
    console.log(a) // [11, 2, 3, 44, 5, 6]
    //说明第一条,数字转为字符串,"11"<"2"<"3"<"44"<"5"<"6"
    
    //例3.数字排序
    var a=[11,2,44,3,5,6];
    a.sort(function(a,b){
        return a-b; //升序——当a<b时,a-b返回一个小于0的值。根据说明2-a,a会在b的前面,则实现了升序排序。反之如果想实现降序排序,return b-a即可。
    });
    console.log(a) //输出 [2, 3, 5, 6, 11, 44]
    
    //例3.随机排序
    var a=[11,2,44,3,5,6];
    a.sort(function(a,b){
        return Math.random()>.5?-1:1; //根据说明2-c特性,实现随机排序
    });
    console.log(a) //每次运行的输出都不同
    

    以上是sort()方法的一些基本用法,MDN里还有更多的用法。下面我们来看看sort()方法到底是如何排序的。

    sort()方法如何实现排序

    怎么查看sort()方法是如果实现排序的呢?我们可以在比较函数里把a,b及数组输出一下,看看是否能够看出使用的排序算法。

    var arr=[1, 8, 3, 5, -1];
    function compare(a,b){
        console.log(a,b,arr);
        return a-b;
    }
    arr.sort(compare);
    /**
    控制台输出
    1 8 [1, 8, 3, 5, -1]
    8 3 [1, 8, 3, 5, -1]
    1 3 [1, 8, 8, 5, -1]
    8 5 [1, 3, 8, 5, -1]
    3 5 [1, 3, 8, 8, -1]
    8 -1 [1, 3, 5, 8, -1]
    5 -1 [1, 3, 5, 8, 8]
    3 -1 [1, 3, 5, 5, 8]
    1 -1 [1, 3, 3, 5, 8]
    [-1,1, 3, 5, 8]
    */
    

    不知道同学们有没有看出什么端倪。反正我一开始是什么都没有发现,那就分析分析咯。
      第一次1和8比较,1<8,不需要调整位置。
      第二次8和3比较,8>3,需要调整位置。但是这里没有交换位置,仅仅是8覆盖了3位置。这里就可以推断出不是单纯的使用了冒泡算法。
      第三是1和3比较,1<3,3替换了8的位置。什么鬼,几个意思???看到这里我也是表示不懂呀。那就继续往下看咯。
      第四是8和5比较,8>5,又仅仅是覆盖,没有交换位置。还是不懂,继续往下!
      第五是3和5比较,3<5,5替换了8的位置,不懂,继续往下!
      第六是8和-1比较,8>-1, 还仅仅是覆盖,继续往下!
      第七、八、九次,-1依次和5,3,1做了比较,并且5,3,1都移动了一次位置。等等,这怎么和插入排序法有点相似。

    再试试一下

    var arr=[1, 8, 9, 5, 2];
    arr.sort(compare);
    /**
    控制台输出
    1 8 [1, 8, 9, 5, 2]
    8 9 [1, 8, 9, 5, 2]
    9 5 [1, 8, 9, 5, 2]
    8 5 [1, 8, 9, 9, 2]
    1 5 [1, 8, 8, 9, 2]
    9 2 [1, 5, 8, 9, 2]
    8 2 [1, 5, 8, 9, 9]
    5 2 [1, 5, 8, 8, 9]
    1 2 [1, 5, 5, 8, 9]
    [1, 2, 5, 8, 9]
    */
    

    没跑了,这就是插入法。再捋捋,第一次冒泡完之后,前两位肯是有序的。第二次比较,如果发生位变化,a先向后移动一位,b没有直接前移,而是通过插入法找到正确的位置插入,此时前三位有序。如果没有发生位置变化,说明此时前三位已经有序,继续拿有序的最后一位和之后的一位比较。如此循环,直至整个数组有序。

    到这里,我们得出了结论:sort()方法是使用的冒泡各插入两种方式结合进行排序的。 如果对排序不熟悉的同学,可以看看——《十大经典排序算法》

    经评论区大神的提醒,EMCAScript并没有定义sort()方法使用的排序算法,各个浏览器实现的方式并不相同。以上的结论我只在chrome和fireFox中存在。以上结论在chrome和fireFox也并不完全正确,当数组长度过长时,就不在是使用冒泡和插入两种方式结合进行排序了,而是使用一种我不了解方法。先修改错误的结论。等我弄清楚那种我不了解的方法,再来更新_srot()方法。

    童鞋你似不似以为到这里就完了,文章就完美结束了?当然不似!!!接下来,闲着没事我们模仿sort(),实现一个和sort()方法功能一样的自定义方法玩玩呀。

    实现一个和sort()方法相似的_sort()方法

    这里不多说,直接上代码。然后看注释

    Array.prototype._sort.f=function(a,b){ //设置默认按照Unicode位点进行排序
        a+="",b+="";
        return a<b?-1:a===b?0:1;
    }
    
    Array.prototype._sort=function(f){
    
        /**
        * 如未传入实参
        * 或传入的实参不是函数
        * 使用默认的排序函数 (按字符顺序)
        */
        var f=f&&typeof(f)=="function"?f:Array.prototype._sort.f,
            len=this.length,
            i=0,
            t;
        /**
        * 这个循环开始排序
        * Array.sort()使用的是一种冒泡各插入结合的排序方法
        * 
        */
        for(i=0,t=undefined;i<len-1;i++){
            
            if(f(this[i],this[i+1])>0){ //大于零则需要交接位置
                t=this[i+1],this[i+1]=this[i];
            }
            
            /**
            * 如果t值是unfeined,
            * 则当前的这次骑比较没有发生位置变化
            * 也就不需要使用插入法了
            */
            if(t){
                //使用插入法找到正确的插入位置,上面排序算法还有优化插入法排序的方法
                for(var j=i-1;j>=0;j--){
                
                    if(f(this[j],t)>0){//如果当前元素大于t,则当前元素后移一位
                    
                        this[j+1]=this[j];
                        
                    }else{//否则表示找到插入点了,插入t,并退出循环
                    
                        this[j+1]=t;
                        t=undefined;//将t设为undefined,防止冒泡未发生替换就进入插入法排序
                        break;
                        
                    }
                }                       
            }           
        }
        return this; //返回排序后的新数组
    }
    

    到这里就完了???No!No!No!虽然我们实现了_sort()方法,但是还有一个不完美的地方。说明第三点说了对undefined的处理规则,我们还没有对unfined进行任何处理呢。还需要在上面的排序循环开始之前添加这样一段。

    //这个循环把所有数组undefined的元素和数组最后一个不是undefined的元素替换
    //不同浏览器对undefined处理方式不同,这里模仿chrome的处理方式
    for(;i<len;i++){ 
    
        if(this[i]===undefined){ //
        
        /**
        * while找到最后一个(len-1)不是undefined的元素的下标
        * 同时更新需要排序的元素个数(len)
        * 那些个undefined就不鸟它了
        * 下标小于i的元素已经检查替换完成了,不需要再重复一次。所以添加一个len>=i的条件
        */
        while(this[len-1]===undefined&&len>=i){ 
            len--;
        }
        
        /**
        * 如果len等于i
        * 就表示下标不小于i的元素都是undefined了
        * 可以不用继续遍历了
        */
        if(len===i) break; 
        
        /**
        * 使用t将最后一个不是undefined的元素保存起来
        * i in this 是判断这个元素是不存在,还是值是undefined
        * 数组中一个不存在的元素,也会返回undefined(稀疏数组)
        * 这两者还是有区别的
        * 如果不存在i in this会返回 false
        */
        t=this[len-1];
        if(i in this)
            this[len-1]=undefined; //元素值为undefined,直接将要替换元素值设为undefined
        else
            delete this[len-1]; //元素不存在,通过删除将要替换的元素设置为不存在,
        
        this[i]=t; //替换undefined元素
        
        //又塞了一个undefinef到后面,所以要排序的元素又少了一个,再减减一下
        len--; 
        
        }
    
    }
    

    到这里是真结束了,谢谢大家!如何有什么我说错了或者没说明白的地方,欢迎大家留言一起讨论,大家一起学习,共同进步么。

    相关文章

      网友评论

      • 小糖一员:ECMAScript规范中没有规定具体的sort算法,V8引擎采用不稳定排序,当属于长度超过10条时。会调用快速排序,10条一下调用插入排序。如果想手动改变排序算法。排序函数返回值的问题要休息
        快减肥成功的胖纸::+1: :+1: get了,刚在chrome中试了一下,数组长度超过20时,确实不在是使用我说的那种方法排序 了。

      本文标题:Array.prototype.sort()方法到底是如何排序的

      本文链接:https://www.haomeiwen.com/subject/qmkftxtx.html