지역 사회 배우다 도구 라이브러리 여가
찾다
한국어
집 > 웹 프론트엔드 > JS 튜토리얼 > 본문

js를 사용하여 다양한 정렬 방법을 구현하는 방법

亚连
풀어 주다： 2018-06-13 17:48:58
원래의
1459명이 탐색했습니다.

아래에서는 다양한 정렬 방법과 js 기반 정렬 방법의 차이점에 대한 기사(자세한 설명)를 공유하겠습니다. 이는 좋은 참고 가치가 있으며 모든 사람에게 도움이 되기를 바랍니다.

오늘 갑자기 생각이 나서 정렬 방법이 다양한 정렬에 비해 장점이 있는지 알고 싶어서 다른 사람의 코드를 참고하여 테스트해 보았습니다. 결과는 다음과 같습니다. 

<!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>
로그인 후 복사

위의 방법은 테스트 시간을 통과한 후 어떤 정렬 방법이 시간을 절약하는지 분석합니다. 올바른 방법을 사용하면 특히 빅데이터를 실행할 때 많은 시간을 절약할 수 있습니다.

먼저 10,000개 길이의 배열을 처리하는 데 걸리는 시간을 살펴보세요.

* sort sort systemSort 11
* bubble sort bubbleSort 169
* Quick sort QuickSort 144
* 삽입 정렬 insertSort 139
* Hill Sort shellSort 3

100,000개 길이의 배열 데이터 테스트:

* sort sort systemSort 63
* Bubble sort bubbleSort 16268
* Quick sort QuickSort는 오류를 직접 보고합니다
* 삽입 정렬 insertSort 13026
* Hill sort shellSor 8시

1백만 길이의 배열 테스트:

* 정렬 정렬 시스템Sort 575
* 버블 정렬 bubbleSort 알 수 없는 시간
* 빠른 정렬 QuickSort 직접 오류 보고
* 삽입 정렬 insertSort 직접 충돌
* Hill 정렬 shellSort 93

1천만 개의 긴 배열 테스트:

* 정렬 정렬 시스템Sort 7039
* 버블 정렬 bubbleSort 테스트 안 됨
* 퀵 정렬 QuickSort 테스트 안 됨
* 삽입 정렬 insertSort 테스트 안 됨
* Hill sort shellSort 1225

1억 길이의 배열 테스트:

* 정렬 정렬 시스템Sort가 직접 충돌함
* 버블 정렬 bubbleSort 테스트 안 됨
* 빠른 정렬 QuickSort 테스트 안 됨
* 삽입 정렬 insertSort 테스트 안 됨
* Hill sort shellSort 19864

최종 통과 최악의 경우 우리는 Hill 정렬이 여전히 최고라는 사실을 발견했고, 이는 시스템의 정렬보다 훨씬 빠르다는 것을 발견했습니다. 이렇게 하면 모든 사람이 상황을 알 수 있습니다. 정렬에는 어떤 방법을 사용해야 합니까? 그런 다음 임의의 조건에서 테스트합니다. 

<!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>
로그인 후 복사
1천만 개의 긴 배열 테스트:

* 정렬 정렬 시스템Sort 8842* 버블 정렬 bubbleSort 테스트되지 않음

* 빠른 정렬 QuickSort 테스트되지 않음

* 삽입 정렬 insertSort 45
* Hill sort shellSort 1133


알 수 없는 상황과 비교적 좋은 상황에서는 삽입 정렬이 가장 효율적입니다

위는 모두를 위해 편집한 내용입니다. 네, 바랍니다. 앞으로 모든 사람에게 도움이 될 것입니다.

관련글 :

vue-admin과 백엔드(flask) 분리 및 결합에 대한 자세한 설명

Vue+webpack에서 기본 구성에 대해 자세히 설명

Vue에서 기본 구성에 대해 자세히 설명 +webpack

nodejs+express 환경에서 다인용 채팅방 만드는 방법

위 내용은 js를 사용하여 다양한 정렬 방법을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

관련 라벨：
js sort 区别 排序
원천：php.cn
이전 기사：JavaScript를 사용하여 추측 게임을 구현하는 방법(자세한 튜토리얼) 다음 기사：Vue에서 CDN 최적화를 사용하는 방법
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
저자별 최신 기사
최신 이슈
여러 경로에 선언된 작업자 풀이 임계값을 고려하지 않고 여전히 CPU 사용량을 유지할 수 있습니까? CPU 집약적인 작업을 처리하기 위해 작업자 풀이 있는 node.js 시스템을 찾고 있지만 여러 경로에서의 CPU 사용량에 대해 약간 혼란스럽습니다. 시나리오는 ...
에서 2024-04-06 19:54:23
0
1
444
d3.js를 확대할 때 산점도 값이 유지되지 않습니다. d3.js를 처음 사용하는 것이므로 양해해 주시기 바랍니다. vue.js 파일에 순수 JavaScript로 구현했습니다. 확대/축소 기능을 사용하여 산점도를 만들...
에서 2024-04-06 18:16:26
0
1
403
숨겨진 측면 패널 표시: 선택됨 애니메이션 햄버거 메뉴를 통해 보기로 전환할 수 있는 탐색 메뉴를 측면 패널에 갖고 싶습니다. JS 없이 CSS만 사용하여 만들고 싶습니다. :checked 의사...
에서 2024-04-06 15:49:33
0
1
319
Nuxt.js로 생성된 대시보드를 배포하기 위해 SSG를 사용해야 합니까? Nuxt.js를 사용하여 내부용 대시보드를 개발하겠습니다. 내부 대시보드이므로 범용 스키마가 필요하지 않습니다. 일반적으로 대부분의 대시보드는 SPA에서 개발됩니...
에서 2024-04-06 13:17:44
0
1
493
Electron은 사전 로드 시 AppData를 가져옵니다. 사전 로드된 AppData 디렉터리를 얻는 방법은 무엇입니까? Background.js[...]asyncfunctioncreateWindow(){constwin=...
에서 2024-04-06 11:05:31
0
1
417
관련 주제
더>
인기 추천
인기 튜토리얼
더>
관련 튜토리얼
인기 추천
최신 강좌
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿