js 各种排序方法和sort方法的区别详解-js教程-PHP中文网

首页

web前端

js教程

js 各种排序方法和sort方法的区别详解

小云云

Jan 05, 2018 pm 05:55 PM

javascript sort 方法

今天突发奇想，想明白sort方法是否比各种排序都有优势，本文主要为大家分享一篇基于js 各种排序方法和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%;
    }
    #p {
      height: 100%;
      width: 100%;
    }
  </style>
</head>
<body>
<p id="p"></p>
<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%;
    }
    #p {
      height: 100%;
      width: 100%;
    }
  </style>
</head>
<body>
<p id="p"></p>
<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

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

热AI工具

热工具

热门话题

gmail邮箱登陆入口在哪里

7541

CakePHP 教程

1381

steam的账户名称是什么格式

win11激活密钥永久

NYT连接提示和答案

显示更多

Related knowledge

怎么删除微信好友？删除微信好友的方法 Mar 04, 2024 am 11:10 AM

微信是主流的聊天工具之一，我们可以通过微信认识新的朋友，联系老的朋友，维系朋友之间的情谊。正如天下没有不散的宴席，人与人之间的相处难免会发生意见不合的时候。当一个人极其影响你的情绪，或者在相处的时候发现三观不合，没办法再继续沟通，那么我们可能需要删除微信好友的方法。怎么删除微信好友？删除微信好友的方法第一步:在微信主界面轻触【通讯录】;第二步:点击对应要删除的好友，进入【详细资料】;第三步:点击右上角【...】;第四步:点击下方【删除】即可;第五步:了解后页面提示后，点击【删除联系人】即可;温馨

怎么在番茄免费小说app中写小说分享番茄小说写小说方法教程 Mar 28, 2024 pm 12:50 PM

　　番茄小说是一款非常热门的小说阅读软件，我们在番茄小说中经常会有新的小说和漫画可以去阅读，每一本小说和漫画都很有意思，很多小伙伴也想着要去写小说来赚取赚取零花钱，在把自己想要写的小说内容编辑成文字，那么我们要怎么样在这里面去写小说呢?小伙伴们都不知道，那就让我们一起到本站本站中花点时间来看写小说的方法介绍吧。分享番茄小说写小说方法教程　　1、首先在手机上打开番茄免费小说app，点击个人中心——作家中心　　2、跳转到番茄作家助手页面——点击创建新书在小说的结

七彩虹主板怎么进入bios？教你两种方法 Mar 13, 2024 pm 06:01 PM

　　七彩虹主板在中国国内市场享有较高的知名度和市场占有率，但是有些七彩虹主板的用户还不清楚怎么进入bios进行设置呢？针对这一情况，小编专门为大家带来了两种进入七彩虹主板bios的方法，快来试试吧！　　方法一：使用u盘启动快捷键直接进入u盘装系统　　七彩虹主板一键启动u盘的快捷键是ESC或F11，首先使用黑鲨装机大师制作一个黑鲨U盘启动盘，然后开启电脑，当看到开机画面的时候，连续按下键盘上的ESC或F11键以后将会进入到一个启动项顺序选择的窗口，将光标移动到显示“USB”的地方，然

微信删除的人如何找回（简单教程告诉你如何恢复被删除的联系人） May 01, 2024 pm 12:01 PM

而后悔莫及、人们常常会因为一些原因不小心将某些联系人删除、微信作为一款广泛使用的社交软件。帮助用户解决这一问题，本文将介绍如何通过简单的方法找回被删除的联系人。1.了解微信联系人删除机制这为我们找回被删除的联系人提供了可能性、微信中的联系人删除机制是将其从通讯录中移除，但并未完全删除。2.使用微信内置“通讯录恢复”功能微信提供了“通讯录恢复”节省时间和精力，用户可以通过该功能快速找回之前被删除的联系人，功能。3.进入微信设置页面点击右下角，打开微信应用“我”再点击右上角设置图标、进入设置页面，，

手机字体大小设置方法（轻松调整手机字体大小） May 07, 2024 pm 03:34 PM

字体大小的设置成为了一项重要的个性化需求，随着手机成为人们日常生活的重要工具。以满足不同用户的需求、本文将介绍如何通过简单的操作，提升手机使用体验，调整手机字体大小。为什么需要调整手机字体大小-调整字体大小可以使文字更清晰易读-适合不同年龄段用户的阅读需求-方便视力不佳的用户使用手机系统自带字体大小设置功能-如何进入系统设置界面-在设置界面中找到并进入"显示"选项-找到"字体大小"选项并进行调整第三方应用调整字体大小-下载并安装支持字体大小调整的应用程序-打开应用程序并进入相关设置界面-根据个人

Win11管理员权限获取方法汇总 Mar 09, 2024 am 08:45 AM

Win11管理员权限获取方法汇总在Windows11操作系统中，管理员权限是非常重要的权限之一，可以让用户对系统进行各种操作。有时候，我们可能需要获取管理员权限来完成一些操作，比如安装软件、修改系统设置等。下面就为大家总结了一些获取Win11管理员权限的方法，希望能帮助到大家。1.使用快捷键在Windows11系统中，可以通过快捷键的方式快速打开命令提

手机版龙蛋孵化方法大揭秘（一步一步教你如何成功孵化手机版龙蛋） May 04, 2024 pm 06:01 PM

手机游戏成为了人们生活中不可或缺的一部分，随着科技的发展。它以其可爱的龙蛋形象和有趣的孵化过程吸引了众多玩家的关注，而其中一款备受瞩目的游戏就是手机版龙蛋。帮助玩家们在游戏中更好地培养和成长自己的小龙，本文将向大家介绍手机版龙蛋的孵化方法。1.选择合适的龙蛋种类玩家需要仔细选择自己喜欢并且适合自己的龙蛋种类，根据游戏中提供的不同种类的龙蛋属性和能力。2.提升孵化机的等级玩家需要通过完成任务和收集道具来提升孵化机的等级，孵化机的等级决定了孵化速度和孵化成功率。3.收集孵化所需的资源玩家需要在游戏中

Oracle版本查询方法详解 Mar 07, 2024 pm 09:21 PM

Oracle版本查询方法详解Oracle是目前世界上最流行的关系型数据库管理系统之一，它提供了丰富的功能和强大的性能，广泛应用于企业中。在进行数据库管理和开发过程中，了解Oracle数据库的版本是非常重要的。本文将详细介绍如何查询Oracle数据库的版本信息，并给出具体的代码示例。查询数据库版本的SQL语句在Oracle数据库中，可以通过执行简单的SQL语句

See all articles

js 各种排序方法和sort方法的区别详解

热AI工具

Undresser.AI Undress

AI Clothes Remover

Undress AI Tool

Clothoff.io

AI Hentai Generator

热门文章

热工具

记事本++7.3.1

SublimeText3汉化版

禅工作室 13.0.1

Dreamweaver CS6

SublimeText3 Mac版

热门话题