网站首页 » 前端开发 » JavaScript » JavaScript 常用的排序方法
上一篇:
下一篇:

JavaScript 常用的排序方法

前言

Javascript 中排序可以说是非常常见的,不管是在平时的开发还是面试中排序都或多或少出现过。虽然说不算多,但是必不可少是肯定的。那么下面我们就来看看Javascript 中的排序方法都有哪些,在这里就不全列出,只把非常常用的分享给大家,其它的其实我觉得你知道有这个方法,并且知道在什么情况下可以用或者在什么情况下不能用就可以了。

原生sort

sort() 方法用于对数组的元素进行排序,在原数组上进行排序,不生成副本。可修改 a 与 b 的位置来实现升序或者降序排序。

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

冒泡排序

从名字就大概知道他的工作原理了,冒泡排序就是把元素两两比对,慢慢的往上冒。我们来看下百科是怎么说的:

原理

1.比较相邻的元素。如果第一个比第二个大,就交换他们两个。

2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

3.针对所有的元素重复以上的步骤,除了最后一个。

4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

function bubbleSort(array){
    var len = array.length, temp;
    for(var i = 0; i<len; i++){
        for(var j=0; j<len-i-1; j++){
            if(array[j] > array[j+1]){
                temp = array[j+1];
                array[j+1] = array[j];
                array[j] = temp;
            }
        }
    }
    return array;
}

插入排序

假定我们要插入的原素为有序,然后把新丢进来的元素跟已排好序的元素进行比较,找到合适的位置再把目标元素放到此合适的位置上(下标)。我们来看看百科的说法。

原理

将n个元素的数列分为已有序和无序两个部分,每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较,找出插入位置,将该元素插入到有序数列的合适位置中。 假设在一个无序的数组中,要将该数组中的数按插入排序的方法从小到大排序。假设啊a[]={3,5,2,1,4};插入排序的思想就是比大小,满足条件交换位置,一开始会像冒泡排序一样,但会比冒泡多一步就是交换后(a[i]=a[i+1]后)原位置(a[i])会继续和前面的数比较满足条件交换,直到a[i+1]前面的数组是有序的。比如在第二次比较后数组变成a[]={2,3,5,1,4};

function insertSort(arr){
    var i,j,temp,arrlen = arr.length;
    for(i=1;i<arrlen;i++){
        temp = arr[i];
        j=i-1;
        while(j>=0 && temp < arr[j]){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = temp;
    }
}

二分插入排序

这种方法是在插入排序的基础上作了改进的,通过二分法来减少对比的次数,来提高性能。

function insertSort(arr){
    var i,temp,end,mid,start,
    arrlen = arr.length;
    for(i=1;i<arrlen;i++){
        temp = arr[i];
        start = 0;
        end = i-1;
        while(end - start > 1){
            mid = Math.ceil((start + end)/2);
            if( temp < arr[mid] ){
                end = mid;
            }else{
                start = mid;
            }
        }
        if(temp < arr[start] || temp == arr[start]){
            for(var j=i;j>=start;j--){
                arr[j] = arr[j-1];
            }
            arr[start] = temp;
        }else if(temp > arr[start] && temp < arr[end]){
            for(var k=i;k>=end;k--){
                arr[k] = arr[k-1];
            }
            arr[end] = temp;
        }
    }
    return arr;
}

性能大比拼

方法不在多,只要效率高就好,所以我们下面来测试下上面几种方法的执行效率。我们先用一个for循环来生成一个10万级元素的数组。

var array = [];
for(var i = 0;i<100000;i++){
    array[i] = parseInt(Math.random() * 1000000);
}

接下来我们就在这个基础上测试各方法之间的性能差异

方法\实验组 1 2 3 4 5 6 7 8 9 10 平均值
方法1 99 84 115 89 99 90 87 93 112 90 94.875
方法2 25057 24347 24300 24456 24320 24427 24378 24347 24485 24298 24382.5
方法3 7823 7794 7816 7896 7886 7927 7841 7817 7802 7887 7846
方法4 9017 8926 8870 8866 8926 8862 8948 8898 8938 8866 8904.75

不比不知道,一比吓一跳。怎么性能相差这么大,其实这个也是可以理解的,毕竟原生的排序肯定会比自己写的在代码效率方面肯定会强很多,但让我最为意外的是,我在自己写出来的插入排序方法跟我自以为优化过的二分插入排序会中,后者会比前者强很多,即使不是强很多,怎么地也得好那么一点点吧,可数据赤裸地就放在哪了。虽然还是不敢相信,但这已经成了不争的事实。我只能好好的反应自己,是不是自己写的代码有问题才导致这个荒谬的结论?请容许我再研究下。

相关资料

Array.prototype.sort()

Date.prototype.getTime()

 

  • 微信扫一扫,赏我

  • 支付宝扫一扫,赏我

声明

原创文章,不经本站同意,不得以任何形式转载,如有不便,请多多包涵!

本文永久链接:http://yunkus.com/javascript-sort-method/

评论8
  1. 克拉米尔的橙子 2016年10月28日 at pm5:34 回复

    脑子贼笨好烦面试

  2. 阿成XX 2016年11月7日 at am11:12 回复

    你学的前端?

  3. 阿成XX 2016年11月7日 at am11:12 回复

    你学的前端?也是应届生?

  4. 云库网 2016年11月24日 at pm2:58 回复

    我也一直被别人拒绝,别人拒绝了你不能代表你笨,只是你还不具备他们所需要的能力而已,只要向着自己的目标努力过了,总是找到好的娘家!一起加油!

  5. 阳光5675在搜狐 2016年12月1日 at am11:08 回复

    博主,请问测试代码运行效率用到时什么方法?console.time可行吗?

  6. 云库网 2016年12月2日 at am8:01 回复

    可以的

  7. 阳光5675在搜狐 2016年12月2日 at am10:15 回复

    好的,正在学习当中。可以将您的文章转载一些到我的博客吗?不做商业用途,记录下来做笔记。

  8. 云库网 2016年12月29日 at pm10:44 回复

    可以的,注明出外就好了!

Leave a Reply

Your email address will not be published. Required fields are marked *

评论 END