데이터 정렬이 가장 빠른 사람은 누구입니까(Array.prototype.sort PK 퀵 정렬 in javascript)

데이터 정렬이 가장 빠른 사람은 누구입니까(Array.prototype.sort PK 퀵 정렬 in javascript)_javascript 기술

WBOY

풀어 주다： 2016-05-16 19:21:10

원래의

1081명이 탐색했습니다.

그런데 저를 놀라게 한 것은 아래 네티즌이 JavaScript에서 Array의 정렬 방법 자체가 가장 빠르고, 퀵 정렬 알고리즘보다 빠르다는 답변을 했다는 것입니다. 작업하는 데 시간이 너무 오래 걸려서 매우 우울했습니다. 오랫동안 정렬 알고리즘에 대해 연구하다가 실제로 Array 자체의 정렬 방법을 잊어버렸습니다
그런데 자바스크립트에 내장된 정렬 방법이 정말 빠른 정렬 알고리즘보다 빠를까요?
하하, 테스트해보면 알 수 있습니다
먼저 테스트 환경에 대해 말씀드리겠습니다
1. 제 테스트 환경은 IE6.0과 firefox2.0입니다
2. 알고리즘마다 차이가 많습니다. 구현 방법. 다음 테스트에서는 위 네티즌이 구현한 퀵 정렬 알고리즘을 선택하고, 내장된 기능만 외부로 옮겼습니다.
3. 알고리즘의 실행 속도는 데이터의 종류, 크기, 양에 따라 다릅니다. I 여기서는 999999보다 작은 정수의 정렬만 비교하며, 데이터 양은 각각 500, 2000, 30000으로 설정됩니다.

정렬 방법 정보: 정렬 방법은 Array에 내장된 방법입니다. javascript에 대한 권위 있는 가이드는 다음과 같이 정의됩니다.

sort( ) 메서드는 배열의 요소를 제자리에 정렬합니다. sort( )가 인수 없이 호출되면 배열의 요소가 만들어지지 않습니다. 배열은 알파벳 순서(보다 정확하게는 문자 인코딩에 따라 결정됨)로 정렬됩니다. 이를 위해 필요한 경우 요소를 먼저 문자열로 변환하여 비교할 수 있습니다. 다른 순서로 요소를 배열하는 경우 두 값을 비교하고 상대적 순서를 나타내는 숫자를 반환하는 비교 함수를 제공해야 합니다. 비교 함수는 두 개의 인수 a와 b를 사용하고 다음 중 하나를 반환해야 합니다.

정렬 방법은 함수 유형 매개변수를 허용할 수 있습니다. 매개변수가 제공되지 않으면 기본값은 문자 순서로 정렬되는 것이므로 정수를 정렬하려면 함수 유형 매개변수를 제공해야 합니다. 이 테스트의 호출 방법은 다음과 같습니다.

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

물론 정렬할 정수의 개수가 매개변수를 제공하지 않고 반환된 결과는 테스트 후에 알 수 있습니다.

코드 복사

코드는 다음과 같습니다. : <script> </span>alert( [3,4,5,11,1].sort()) </div>alert([3,4,5,11,1 ].sort(function(a,b){return a-b})) <div class="codebody" id="code37955"></script>

프롬프트: 먼저 수정한 후 실행하면 됩니다.
결과는 [1, 11, 3, 4, 5] 이는 분명히 우리가 원하는 결과가 아닙니다.
는 정렬이 필요한 배열을 생성합니다. 공정한 결과를 얻기 위해 먼저 정렬에 사용되는 배열을 생성합니다. 두 방법에서 사용되는 배열은 각 비교에서 동일한 요소를 갖습니다. 아래는 무작위 배열을 생성하는 코드입니다

코드 복사

코드는 다음과 같습니다. function random(m,n){ //m과 n 사이의 정수 생성

var i=Math.random()

return Math.round((n-m)*i m); 
} 

function getRandomArr(m,n,l){ 
//m: 임의의 정수 n의 최소값을 생성합니다. 생성된 임의 정수의 최대값, l: 생성된 배열의 길이 
var resultArr=[] 
for(var i=0;iresultArr.push(random (m,n)) 
} 
return resultArr; 
} 

 
빠른 정렬 알고리즘 구현, 이 알고리즘은 51js 포럼의 네티즌 구현에서 가져왔습니다. 봤는데, 코드는 다음과 같습니다. 

코드 복사

코드는 다음과 같습니다. function doSort(a,s,e ) {

if(s{
var pos=partition(a,s,e)
doSort(a,s, pos-1);
doSort(a,pos 1,e);
}
}
function partition(a,st,en)
{
var s=st;
var e=en 1 ;
var temp=a[s];
while(1)
{
while(a[ s] 임시)
if(s>e)break
var tem=a[s]
a [e]=tem;
}
a[st]=a[e];
a[e]=temp
return e; .prototype.quickSort=function() {
doSort(this,0,this.length-1);
}

array.join()을 사용하여 결과가 올바른지 확인하세요. . 성능 테스트 코드는 다음과 같습니다.

코드 복사