基于js 各种排序方法和sort方法的区别(详解)

今天突发奇想,想明白sort方法是否比各种排序都有优势,所以就参考别人的代码,做了一个测试,结果令人惊讶啊,上代码。

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width,initial-scale=1.0,maximum-scale=1.0,user-scalable=0">
  <title>图片列表生成交互组件</title>
  <style>
    * {
      margin: 0;
      border: 0;
    }
    html, body {
      height: 100%;
    }
    #div {
      height: 100%;
      width: 100%;
    }
  </style>
</head>
<body>
<div id="div"></div>
<script src="myNeedExtend.js"></script>
<script>
  // ---------- 一些排序算法
  Sort = {
    // 利用sort进行排序
    systemSort:function(array){
      return array.sort(function(a, b){
        return a - b;
      });
    },
    // 冒泡排序
    bubbleSort:function(array){
      var i = 0, len = array.length,
        j, d;
      for(; i<len; i++){
        for(j=0; j<len; j++){
          if(array[i] < array[j]){
            d = array[j];
            array[j] = array[i];
            array[i] = d;
          }
        }
      }
      return array;
    },
    // 快速排序
    quickSort:function(array){
      //var array = [8,4,6,2,7,9,3,5,74,5];
      //var array =[0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7];
      var i = 0;
      var j = array.length - 1;
      var Sort = function(i, j){
        // 结束条件
        if(i == j ){ return };
        var key = array[i];
        var tempi = i; // 记录开始位置
        var tempj = j; // 记录结束位置
        while(j > i){
          // j <<-------------- 向前查找
          if(array[j] >= key){
            j--;
          }else{
            array[i] = array[j]
            //i++ ------------>>向后查找
            while(j > ++i){
              if(array[i] > key){
                array[j] = array[i];
                break;
              }
            }
          }
        }
        // 如果第一个取出的 key 是最小的数
        if(tempi == i){
          Sort(++i, tempj);
          return ;
        }
        // 最后一个空位留给 key
        array[i] = key;
        // 递归
        Sort(tempi, i);
        Sort(j, tempj);
      }
      Sort(i, j);
      return array;
    },
    // 插入排序
    insertSort:function(array){
      // http://baike.baidu.com/image/d57e99942da24e5dd21b7080
      // http://baike.baidu.com/view/396887.htm
      // var array = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7];
      var i = 1, j, temp, key, len = array.length;
      for(; i < len; i++){
        temp = j = i;
        key = array[j];
        while(--j > -1){
          if(array[j] > key){
            array[j+1] = array[j];
          }else{
            break;
          }
        }
        array[j+1] = key;
      }
      return array;
    },
    // 希尔排序
    shellSort:function(array){
      // http://zh.wikipedia.org/zh/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F
      // var array = [13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10];
      // var tempArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1];
      // reverse() 在维基上看到这个最优的步长 较小数组
      var tempArr = [1031612713, 217378076, 45806244, 9651787, 2034035, 428481, 90358, 19001, 4025, 836, 182, 34, 9, 1];
      //针对大数组的步长选择
      var i = 0;
      var tempArrLength = tempArr.length;
      var len = array.length;
      var len2 = parseInt(len/2);
      for(;i < tempArrLength; i++){
        if(tempArr[i] > len2){
          continue;
        }
        tempSort(tempArr[i]);
      }
      // 排序一个步长
      function tempSort(temp){
        //console.log(temp) 使用的步长统计
        var i = 0, j = 0, f, tem, key;
        var tempLen = len%temp > 0 ? parseInt(len/temp) + 1 : len/temp;
        for(;i < temp; i++){// 依次循环列
          for(j=1;/*j < tempLen && */temp * j + i < len; j++){
            //依次循环每列的每行
            tem = f = temp * j + i;
            key = array[f];
            while((tem-=temp) >= 0){
              // 依次向上查找
              if(array[tem] > key){
                array[tem+temp] = array[tem];
              }else{
                break;
              }
            }
            array[tem + temp ] = key;
          }
        }
      }
      return array;
    }
  };
  testArrs = [];
  for (var i = 10000000; i > 0; i--) {
    testArrs.push(i);
  }
  function test(fun,arr) {
    console.log(arr);
    var oldTime = +new Date();
    var new_arr = Sort[fun](arr);
    var newTime = +new Date();
    console.log(new_arr);
    console.log(newTime-oldTime);
  }
  /*
  * sort排序 systemSort
  * 冒泡排序 bubbleSort
  * 快速排序 quickSort
  * 插入排序 insertSort
  * 希尔排序 shellSort
  *
  * */
  test("systemSort",testArrs);
</script>
</body>
</html>

上面的方法通过测试时间,然后分析哪个排序方法省时,时间就是生命,用对正确的方法,就能省下好多时间,尤其是大数据运行的时候。

首先看运行处理10000个长度数组时的所用的时间:

* sort排序 systemSort 11
* 冒泡排序 bubbleSort 169
* 快速排序 quickSort 144
* 插入排序 insertSort 139
* 希尔排序 shellSort 3

测试十万长的数组数据:

* sort排序 systemSort 63
* 冒泡排序 bubbleSort 16268
* 快速排序 quickSort 直接报错
* 插入排序 insertSort 13026
* 希尔排序 shellSort 8

测试一百万的长度的数组:

* sort排序 systemSort 575
* 冒泡排序 bubbleSort 时间未知
* 快速排序 quickSort 直接报错
* 插入排序 insertSort 直接崩溃
* 希尔排序 shellSort 93

测试一千万长的数组:

* sort排序 systemSort 7039
* 冒泡排序 bubbleSort 没测
* 快速排序 quickSort 没测
* 插入排序 insertSort 没测
* 希尔排序 shellSort 1225

测试一亿长的数组:

* sort排序 systemSort 直接崩溃
* 冒泡排序 bubbleSort 没测
* 快速排序 quickSort 没测
* 插入排序 insertSort 没测
* 希尔排序 shellSort 19864

最后通过测试,在最坏的情况下,发现希尔排序还是最好,竟然比系统的sort排序都快,确实令人惊讶,大家这样就能看出来在什么情况需要使用什么方法进行排序了吧

然后我们进行随机情况进行测试:

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width,initial-scale=1.0,maximum-scale=1.0,user-scalable=0">
  <title>图片列表生成交互组件</title>
  <style>
    * {
      margin: 0;
      border: 0;
    }
    html, body {
      height: 100%;
    }
    #div {
      height: 100%;
      width: 100%;
    }
  </style>
</head>
<body>
<div id="div"></div>
<script src="myNeedExtend.js"></script>
<script>
  // ---------- 一些排序算法
  Sort = {
    // 利用sort进行排序
    systemSort:function(array){
      return array.sort(function(a, b){
        return a - b;
      });
    },
    // 冒泡排序
    bubbleSort:function(array){
      var i = 0, len = array.length,
        j, d;
      for(; i<len; i++){
        for(j=0; j<len; j++){
          if(array[i] < array[j]){
            d = array[j];
            array[j] = array[i];
            array[i] = d;
          }
        }
      }
      return array;
    },
    // 快速排序
    quickSort:function(array){
      //var array = [8,4,6,2,7,9,3,5,74,5];
      //var array =[0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7];
      var i = 0;
      var j = array.length - 1;
      var Sort = function(i, j){
        // 结束条件
        if(i == j ){ return };
        var key = array[i];
        var tempi = i; // 记录开始位置
        var tempj = j; // 记录结束位置
        while(j > i){
          // j <<-------------- 向前查找
          if(array[j] >= key){
            j--;
          }else{
            array[i] = array[j]
            //i++ ------------>>向后查找
            while(j > ++i){
              if(array[i] > key){
                array[j] = array[i];
                break;
              }
            }
          }
        }
        // 如果第一个取出的 key 是最小的数
        if(tempi == i){
          Sort(++i, tempj);
          return ;
        }
        // 最后一个空位留给 key
        array[i] = key;
        // 递归
        Sort(tempi, i);
        Sort(j, tempj);
      }
      Sort(i, j);
      return array;
    },
    // 插入排序
    insertSort:function(array){
      // http://baike.baidu.com/image/d57e99942da24e5dd21b7080
      // http://baike.baidu.com/view/396887.htm
      // var array = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7];
      var i = 1, j, temp, key, len = array.length;
      for(; i < len; i++){
        temp = j = i;
        key = array[j];
        while(--j > -1){
          if(array[j] > key){
            array[j+1] = array[j];
          }else{
            break;
          }
        }
        array[j+1] = key;
      }
      return array;
    },
    // 希尔排序
    shellSort:function(array){
      // http://zh.wikipedia.org/zh/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F
      // var array = [13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10];
      // var tempArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1];
      // reverse() 在维基上看到这个最优的步长 较小数组
      var tempArr = [1031612713, 217378076, 45806244, 9651787, 2034035, 428481, 90358, 19001, 4025, 836, 182, 34, 9, 1];
      //针对大数组的步长选择
      var i = 0;
      var tempArrLength = tempArr.length;
      var len = array.length;
      var len2 = parseInt(len/2);
      for(;i < tempArrLength; i++){
        if(tempArr[i] > len2){
          continue;
        }
        tempSort(tempArr[i]);
      }
      // 排序一个步长
      function tempSort(temp){
        //console.log(temp) 使用的步长统计
        var i = 0, j = 0, f, tem, key;
        var tempLen = len%temp > 0 ? parseInt(len/temp) + 1 : len/temp;
        for(;i < temp; i++){// 依次循环列
          for(j=1;/*j < tempLen && */temp * j + i < len; j++){
            //依次循环每列的每行
            tem = f = temp * j + i;
            key = array[f];
            while((tem-=temp) >= 0){
              // 依次向上查找
              if(array[tem] > key){
                array[tem+temp] = array[tem];
              }else{
                break;
              }
            }
            array[tem + temp ] = key;
          }
        }
      }
      return array;
    }
  };
  testArrs = [];
  for (var i = 0; i < 10000000; i++) {
    testArrs.push(Math.random());
  }
  function test(fun,arr) {
    var oldTime = +new Date();
    var new_arr = Sort[fun](arr);
    var newTime = +new Date();
    console.log(fun);
    console.log(newTime-oldTime);
  }
  /*
  * sort排序 systemSort
  * 冒泡排序 bubbleSort
  * 快速排序 quickSort
  * 插入排序 insertSort
  * 希尔排序 shellSort
  *
  * */
  test("systemSort",testArrs);
  //test("bubbleSort",testArrs);
  //test("quickSort",testArrs);
  test("insertSort",testArrs);
  test("shellSort",testArrs);
</script>
</body>
</html>

测试一千万长的数组:

* sort排序 systemSort 8842
* 冒泡排序 bubbleSort 没测
* 快速排序 quickSort 没测
* 插入排序 insertSort 45
* 希尔排序 shellSort 1133

在未知的情况和比较好的情况下,插入排序的效率最高

以上这篇基于js 各种排序方法和sort方法的区别(详解)就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • js的各种排序算法实现(总结)

    如下所示: // ---------- 一些排序算法 var Sort = {} Sort.prototype = { // 利用sort进行排序 systemSort:function(array){ return array.sort(function(a, b){ return a - b; }); }, // 冒泡排序 bubbleSort:function(array){ var i = 0, len = array.length, j, d; for(; i<len; i++){ f

  • JavaScript中三种常见的排序方法

    1.快速排序: <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>快速排序</title> </head> <body> <script> var ary=[21,8,4,32,5]; function quickSort(ary){ if(ary.length<=

  • js中数组排序sort方法的原理分析

    本文实例分析了js中数组排序sort方法的原理.分享给大家供大家参考.具体分析如下: 最近在百度的项目中要用到对数组进行排序,当然一开始自然想到了数组的sort方法,这方法应用非常简单,大致如下: 复制代码 代码如下: window.onload=function(){         var arr=[2,55,55,1,75,3,9,35,70,166,432,678,32,98];         var arr2=["George","John","

  • JS中sort函数排序用法实例分析

    本文实例讲述了JS中sort函数排序用法.分享给大家供大家参考,具体如下: 最近遇到了一个面试题目,关于排序的问题,为了完善自己的知识点,这里就写一下学习笔记 <html> <head> <TITLE>class_obj_js_class</TITLE> <script language=javaScript> //sort()方法默认是按照ASCII码大小排序,看下面两个例子 function sortDemo(){ var a, l; //

  • 基于js 各种排序方法和sort方法的区别(详解)

    今天突发奇想,想明白sort方法是否比各种排序都有优势,所以就参考别人的代码,做了一个测试,结果令人惊讶啊,上代码. <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width,initial-scale=1.0,max

  • StringUtils里的isEmpty方法和isBlank方法的区别详解

    前言 我们常说的字符串为空,其实就是一个没有字符的空数组.比如: String a = ""; a 就可以称为是一个空字符串.由于 String 在 Java 中底层是通过 char 数组去存储字符串的,所以空字符串对应的 char 数组表现形式为 private final char value[] = new char[0]; 但实际工作中,我们需要对字符串进行一些校验,比如:是否为 null,是否为空,是否去掉空格.换行符.制表符等也不为空.我们一般都是通过一些框架的工具类去做这

  • js截取字符串的两种方法及区别详解

    var long2="1988-0w-07"; alert(long2.substring(0,4)+"------"+long2.substring(5,6));   1988------0 alert(long2.substr(0,4)+"------"+long2.substr(5,2));            1988-----0w substring 截取的时候坐标  包括前边  不包括后边 substr    截取字符串前边参数的坐

  • js中scrollTop()方法和scroll()方法用法示例

    本文实例讲述了js中scrollTop()方法和scroll()方法用法.分享给大家供大家参考,具体如下: 设置滚动条据顶部的高度: $("div").scrollTop(100); //把 scroll top offset 设置为 100px 获得滚动条的高度: $("div").scrollTop()://获得 scroll top offset 触发滚动事件 $(selector).scroll() 将函数绑定到滚动事件中: $(selector).scro

  • 基于js 字符串indexof与search方法的区别(详解)

    1.indexof方法 indexOf() 方法可返回某个指定的字符串值在字符串中首次出现的位置. 语法: 注意:有可选的参数(即设置开始的检索位置). 2.search方法 search() 方法用于检索字符串中指定的子字符串,或检索与正则表达式相匹配的子字符串. 注意:search方法可以根据正则表达式查找指定字符串(可以忽略大小写,并且不执行全局检索),同时没有可选参数(即设置开始的检索位置). 以上这篇基于js 字符串indexof与search方法的区别(详解)就是小编分享给大家的全部

  • 对Keras中predict()方法和predict_classes()方法的区别说明

    1 predict()方法 当使用predict()方法进行预测时,返回值是数值,表示样本属于每一个类别的概率,我们可以使用numpy.argmax()方法找到样本以最大概率所属的类别作为样本的预测标签. 2 predict_classes()方法 当使用predict_classes()方法进行预测时,返回的是类别的索引,即该样本所属的类别标签.以卷积神经网络中的图片分类为例说明,代码如下: 补充知识:keras中model.evaluate.model.predict和model.predi

  • Java排序的那些事之sort方法的使用详解

    目录 引言 升序 数组 集合 降序 声明一个类实现接口 匿名内部类实现接口 Lambda表达式实现接口 自定义数据类型的排序 总结: 引言 在学习Java过程中,排序sort是我们常用的功能:在Java里,数组有Arrays.sort()可以排序,集合则是Collections.sort()方法排序:默认情况下是升序排列,但是降序又该怎么排?又可以通过哪几种方法呢?自定义类型又该怎么做? 下面就来介绍一下sort方法的使用: 升序 升序是默认情况下的,所以这里就简单展示一下使用的方法: 数组 数

  • C#中Abstract方法和Virtual方法的区别

    简介: c#中Abstract和Virtual比较容易混淆,都与继承有关,并且涉及override的使用.virtual可以被子类重写,而abstract必须被子类重写.virtual修饰的方法必须有实现(哪怕是仅仅添加一对大括号),而abstract修饰的方法一定不能实现.它们有一个共同点:如果用来修饰方法,前面必须添加public,要不然就会出现编译错误:虚拟方法或抽象方法是不能私有的.毕竟加上virtual或abstract就是让子类重新定义的,而private成员是不能被子类访问的.下面

  • 详解java中List中set方法和add方法的区别

    目录 前言 相同点 不同点 总结 前言 在Java中的常用的集合接口List中有两个非常相似的方法: E set(int index, E element); void add(int index, E element); 这两个方法都是在集合的指定位置插入指定的元素,那么这两个方法到底有什么区别呢?接下来我们通过ArrayList这个我们常用集合实现来看一下这两个方法的差异 相同点 首先我们来看一下这两个方法在ArrayList中的相同点 他们都会在集合的指定位置插入新的元素,例如下面的例子:

  • JS处理数据四舍五入(tofixed与round的区别详解)

    1 .tofixed方法 toFixed() 方法可把 Number 四舍五入为指定小数位数的数字.例如将数据Num保留2位小数,则表示为:toFixed(Num):但是其四舍五入的规则与数学中的规则不同,使用的是银行家舍入规则,银行家舍入:所谓银行家舍入法,其实质是一种四舍六入五取偶(又称四舍六入五留双)法.具体规则如下: 简单来说就是:四舍六入五考虑,五后非零就进一,五后为零看奇偶,五前为偶应舍去,五前为奇要进一. 显然这种规则不符合我们平常在数据中处理的方式.为了解决这样的问题,可以自定义

随机推荐