小试牛刀之sort()排序的实现

2018-11-15 admin

受大学室友的鼓动,我也打算利用公众平台来记录自己的前端知识积累,同时呢,自己总结的东西,总归会有局限性,希望小伙伴能给我指点迷津。知识就是一张巨大的网,作为一名摸不清头绪的入学者,唯一能做的事情就是吐好每一根丝,丝拧成线,线再织成网。好啦,开机仪式over,废话不多说了啦…


关于Sort()这个函数,决定研究它是因为在看阮老师的箭头函数时,最后有一个小练习: 请使用箭头函数简化排序时传入的函数:

var arr = [10, 20, 1, 2];
arr.sort((x, y) => {
    ???
});
console.log(arr); // [1, 2, 10, 20]

因为之前js基础也不扎实,没有get到这个题的核心,想了想写了写,最后放弃了,看了评论里的答案。我的天,就一句——return x - y;,当时我就觉得这个函数太神奇了,这么简单的解决了数组排序。(上大学那会,懒惰致死的我所有排序算法原理都明明白白,但是从来没有写过,于是就…后悔莫及阿)

sort()函数定义

了解原理先从函数定义入手,于是乎…从W3C上搬了一段解释:

定义和用法: sort() 方法用于对数组的元素进行排序。

语法: arrayObject.sort(sortby)

返回值: 对数组的引用。请注意,数组在原数组上进行排序,不生成副本。

说明:

  1. 如果调用该方法时没有使用参数,将按字母顺序对数组中的元素进行排序,说得更精确点,是按照字符编码的顺序进行排序。要实现这一点,首先应把数组的元素都转换成字符串(如有必要),以便进行比较。
  2. 如果想按照其他标准进行排序,就需要提供比较函数,该函数要比较两个值,然后返回一个用于说明这两个值的相对顺序的数字。比较函数应该具有两个参数 a 和 b,其返回值如下: 若 a 小于 b,在排序后的数组中 a 应该出现在 b 之前,则返回一个小于 0 的值。 若 a 等于 b,则返回 0。 若 a 大于 b,则返回一个大于 0 的值。

sort排序的过程中发生了什么呢

此处参考了前辈的文章链接描述,我就特别傻,断点打到sort()函数这一行,然后step-into执行,不断在console里打印arr。。。傻的一p 怎么查看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都移动了一次位置。

我们得出了结论:sort()方法是使用的冒泡和插入两种方式结合进行排序的。

回顾冒泡和插入排序

这里我用自己的话总结一下: 冒泡排序:

  1. 第一轮:从第一个元素开始,相邻元素比较,前者比后者大,互换位置,下标加一;再继续相邻元素比较,大的元素移到后面,下标加一再比较…这样一轮比较下来,最后一个元素一定是数组里最大的元素
  2. 第二轮及之后:好啦,现在最后一个元素(即最大的元素)确定了,将其排除在外,我们再来从头对比除它之外的元素,将倒数第二大的元素移到倒数第二个位置。以此类推,每一轮确定一个元素的位置,就像小鱼吐泡泡一样,大的泡泡一点一点往上移
function bubbel(arr) {
    var len=arr.length;
    for(var i=0; i<len; i++) {
        for(var j=0; j<len; j++) {
            if(arr[j] > arr[j+1]) {
                var temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;
}

插入排序: 1.第一轮:将第一个元素看成只有一个元素的有序数组,拿第二个元素和它比较,比它小就插到它前面,比它大就插到它后面。 2.第二轮:经过第一轮,前两个元素已为有序数组。再拿第三个元素和前两个元素比较,看插在哪合适。以此类推。一般会新建一个数组记录排序后的数组。

// 插入排序 从下标1开始每增1项排序一次,越往后遍历次数越多
function sort1(array) {
  var len = array.length,
      i, j, tmp, result;

  // 设置数组副本
  result = array.slice(0);
  for(i=1; i < len; i++){
    tmp = result[i];
    j = i - 1;
    while(j>=0 && tmp < result[j]){
      result[j+1] = result[j];
      j--;
    }
    result[j+1] = tmp;
  }
  return result;
}

sort()的正面目来啦

前面铺垫了这么多,终于到了今天的重点——冒泡排序和插入排序是如何混合使用的?即sort()实现的原理。先上我的代码!! 时隔多年,我终于不再懒惰,勇敢写出我的代码。希望努力不要太晚~

var arr = [1, 8, 3, 5, -1];
    var len = arr.length;
    function compareSet(temp, compare_i){
        for(var i = compare_i; i > 0; i--){
            if(temp > arr[i-1]){
                arr[i] = temp;
                break;
            }
            else{
                arr[i] = arr[i-1];
                arr[i-1] = temp;
            }
        }
    }
    for(var i = 0; i < len; i++){
        if(arr[i] > arr[i+1]){
            var temp = arr[i+1];
            arr[i+1] = arr[i];
            console.log(arr);            
            compareSet(temp, i);
        }

    }
    console.log(arr);

根据之前分析sort()排序控制台输出,先是像冒泡排序那样相邻的元素比较。**但是,一旦出现需要换位置的操作时,不再是像插入排序那样直接交换。**而是先用变量temp暂存arr[i+1],再将较大的arr[i]移到[i+1]位置上,对暂存变量temp使用插入排序,将其插入前0 ~ [i-1]有序数组中。把这个temp安排好,再继续之前的冒泡排序。 冒泡排序是元素对调后这一轮就不管事了,要重复i-1轮冒泡。 插入排序是不管现有元素的顺序是否正确,都给你在已有序数组从头比较到尾。 所以,混合起来666。

这里还有一个前辈写的sort()实现,我对比一下,我的运行速度18ms,前辈的25ms。其实我感觉我写的没有前辈的简洁,但不知道为什么我的快一些。之后再仔细研究研究。

            [function findMinIndex(arr,start){
                var iMin=arr\[start\];
                var iMinIndex=start;
                for(var i=start;i<arr.length;i++){
                    if(iMin>arr\[i\]){
                        iMin=arr\[i\];
                        iMinIndex=i;
                    }
                }
                return iMinIndex;
            }
            for(var i=0;i<arr.length;i++){
                var n=findMinIndex(arr,i);
                var tem;
                tem=arr\[n\];
                arr\[n\]=arr\[i\];
                arr\[i\]=tem;
            }][1]

其实,写到这里,应该结束了!但是我忽然想起来,大学《数据结构》课上,我最喜欢的魏莱老师好像给我们说过这个混合排序算法的。老师一步步引导我们思考的场景还历历在目,我甚至都可以回想起老师说话时的语气。可是,我却还的差不多了,实在是可恶!!!

原文链接:https://segmentfault.com/a/1190000017026510

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。

转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]

本文地址:https://www.javascriptcn.com/read-45555.html

文章标题:小试牛刀之sort()排序的实现

相关文章
vue+element-ui+slot-scope实现可编辑表格
1.咱开发拿到需求大多数是去网上找成型的组件,找不到再看原生的方法能否实现,大牛除外哈,大牛一般喜欢封装组件框架。 2.可编辑表格在后台管理系统还是比较常用的,因为比较流行框架element,iview都没有这个应用,所以考虑了两种方法,下...
2017-12-25
Android中Okhttp3实现上传多张图片同时传递参数
之前上传图片都是直接将图片转化为io流传给服务器,没有用框架传图片。 最近做项目,打算换个方法上传图片。 Android发展到现在,Okhttp显得越来越重要,所以,这次我选择用Okhttp上传图片。 Okhttp目前已经更新到Okhttp...
2017-03-17
JavaScript实现PC手机端和嵌入式滑动拼图验证码三种效果
PC和手机端网站滑动拼图验证码效果源码,同时包涵了弹出式Demo,使用ajax形式提交二次验证码所需的验证结果值,嵌入式Demo,使用表单形式提交二次验证所需的验证结果值,移动端手动实现弹出式Demo三种效果 首先要确认前端使用页面,比如...
2017-03-17
css布局的各种FC简单介绍:BFC,IFC,GFC,FFC
什么是FC? Formatting Context,格式化上下文,指页面中一个渲染区域,拥有一套渲染规则,它决定了其子元素如何定位,以及与其他元素的相互关系和作用。 BFC 什么是BFC Block Formatting Context,块...
2018-05-17
从2014年的发展来展望JS的未来将会如何
&lt;font face=&quot;寰�杞�闆呴粦, Arial, sans-serif &quot;&gt;2014骞达紝杞�浠惰�屼笟鍙戝睍杩呴€燂紝鍚勭�嶈��瑷€灞傚嚭涓嶇┓锛屼互婊¤冻鐢ㄦ埛涓嶆柇鍙樺寲鐨勯渶姹傘€傝繖浜涜��...
2015-11-12
Vue.js组件tab实现选项卡切换
本文实例为大家分享了vue插件tab选项卡的具体代码,供大家参考,具体内容如下 效果图: 代码如下: &lt;!DOCTYPE html&gt; &lt;html lang=&quot;en&quot;&gt; &lt;head&gt; ...
2017-03-13
12个你未必知道的CSS小知识
虽然CSS并不是一种很复杂的技术,但就算你是一个使用CSS多年的高手,仍然会有很多CSS用法/属性/属性值你从来没使用过,甚至从来没听说过。 1.CSS的color属性并非只能用于文本显示 对于CSS的color属性,相信所有Web开发人员...
2015-11-12
ajax为什么令人惊异?ajax的优缺点
使用Ajax的最大优点,就是能在不更新整个页面的前提下维护数据。这使得Web应用程序更为迅捷地回应用户动作,并避免了在网络上发送那些没有改变的信息。 Ajax不需要任何浏览器插件,但需要用户允许JavaScript在浏览器上执行。就像DHT...
2015-11-12
HTML5的5个不错的开发工具推荐
HTML5规范终于在今年正式定稿,对于从事多年HTML5开发的人员来说绝对是一个重大新闻。数字天堂董事长,DCloud CEO王安也发表了文章,从开发者和用户两个角度分析了HTML对两个人群的优势。其实,关于HTML5的开发工具,我们以往的...
2015-11-12
JavaScript教程:JS中的原型
Keith Peters 几年前发表的一篇博文,关于学习没有“new”的世界,其中解释了使用原型继承代替构造函数。两者都是纯粹的原型编码。 标准方法(The Standard Way) 一直以来,我们学习的在 JavaScript 里创建对...
2015-11-12
回到顶部