JavaScript는 빠른 정렬 분석을 구현합니다.-JS 튜토리얼-php.cn

JavaScript는 빠른 정렬 분석을 구현합니다.

小云云

풀어 주다： 2018-01-11 09:06:27

원래의

1737명이 탐색했습니다.

본 글은 주로 자바스크립트에서 퀵 정렬을 구현하는 방법을 소개하며, 퀵 정렬의 원리와 구현 방법, 관련 동작 주의사항을 예시 형태로 분석해 도움이 필요한 분들에게 도움이 되었으면 좋겠습니다.

아이디어:

분할 및 정복 사고와 재귀적 방법을 통해 데이터를 더 작은 요소와 더 큰 요소를 포함하는 여러 하위 시퀀스로 분해합니다.

1 배열의 요소를 기본으로 선택합니다

2. , 벤치마크보다 작은 요소는 벤치마크의 왼쪽으로 이동하고, 벤치마크보다 큰 요소는 벤치마크의 오른쪽으로 이동합니다.

3. 벤치마크의 왼쪽과 오른쪽에 있는 두 하위 집합에 대해 처음 두 단계를 반복합니다. 모든 하위 집합에 요소가 하나만 남을 때까지

구현 코드:

function sqort(arr){
 if(arr.length===0){
 return [];
}
var left=[];
var right=[];
var pivot=arr[0];//(基准以首元素)
for(var i=1;i<arr.length;i++){
 if(arr[i]<pivot){
 left.push(arr[i]);
}else{
 right.push(arr[i]);
}
}
return sqort(left).concat(pivot,qsort(right));//递归
}
var a=[];
for (i=0;i<10;++i){
a[i]=Math.floor(Math.random()*100+1);
}
console.log(a);
console.log(sqort(a));
//(基准以中间元素的情况)
function sqort(arr){
 if(arr.length<=1){
 return arr;
}
var left=[];
var right=[];
var pivotIndex=Math.floor(arr.length/2);
var pivot=arr.splice(pivotIndex,1)[0];//(基准以中间元素)
for(var i=1;i<arr.length;i++){
 if(arr[i]<pivot){
 left.push(arr[i]);
}else{
 right.push(arr[i]);
}
}
return sqort(left).concat(pivot,sqort(right));//递归
}
var a=[12,34,23,78,34,26];
console.log(a);
console.log(sqort(a));

로그인 후 복사

참고: 더 작은 배열과 더 큰 배열에 대해 각각 sqort() 함수를 재귀적으로 호출하세요. 더 작은 배열은 기본 배열과 더 큰 배열을 결합하여 최종 정렬 배열을 형성하고 반환됩니다.