Javascript 퀵 정렬 알고리즘에 대한 자세한 설명_기본지식

퀵 정렬은 버블 정렬을 개선한 것입니다. 원패스 정렬을 통해 정렬할 데이터를 두 개의 독립적인 부분으로 나눕니다. 한 부분의 모든 데이터는 다른 부분의 모든 데이터보다 작습니다. 그런 다음 이 방법을 사용하여 전체 데이터를 각각 빠르게 정렬합니다. 정렬 과정은 재귀적으로 진행될 수 있으며, 최종적으로 전체 데이터는 정렬된 시퀀스가 ​​됩니다.

정렬할 배열이 A[0]...A[N-1]이라고 가정합니다. 먼저 데이터(보통 배열의 첫 번째 숫자)를 벤치마크 데이터로 무작위로 선택한 다음 더 작은 숫자를 모두 선택합니다. 그것을 앞에 두고, 그보다 큰 숫자는 모두 뒤에 놓는다. 이 과정을 원패스 퀵 정렬(one-pass Quick Sort)이라고 한다. 퀵 정렬은 안정적인 정렬 알고리즘이 아니라는 점, 즉 여러 개의 동일한 값의 상대적 위치가 알고리즘 종료 시 변경될 수 있다는 점은 주목할 가치가 있습니다.
원패스 퀵 정렬의 알고리즘은 다음과 같습니다.
1) 정렬이 시작될 때 두 개의 변수를 설정합니다: low=0, high=N-1; 2) 첫 번째 배열 요소를 참조 데이터로 사용하고 이를 베이스에 할당합니다. 즉, base=A[0]
3) high에서 정방향으로 검색, 즉 뒤에서 정방향으로 검색(high--)하고, base보다 작은 첫 번째 값 A[high]를 찾아 A[high]와 A[low]를 교환합니다. 4) low에서 역방향 검색, 즉 앞에서 뒤(low)로 검색하여 base보다 큰 첫 번째 A[low]를 찾아 A[low]와 A[high]를 교환합니다.
5) 낮음=높음이 될 때까지 3단계와 4단계를 반복합니다.

코드 복사 코드는 다음과 같습니다.

함수 분할(요소, 낮음, 높음){

//기본적으로 왼쪽의 첫 번째 요소가 기본 요소로 사용됩니다.
var 기본=요소[낮음];
while(낮음 //기본 요소보다 작은 요소를 찾을 때까지 뒤에서 앞으로 검색하여 교환
반면(낮음 = 기본) 높음--;
var swap1=요소[낮음];요소[낮음]=요소[높음];요소[높음]=swap1;
//기본 요소보다 큰 요소를 찾을 때까지 앞에서 뒤로 검색하여 교환
반면(낮음 var swap2=요소[낮음];요소[낮음]=요소[높음];요소[높음]=swap2;
}
//참조 요소의 위치를 ​​시퀀스의 분할 위치로 반환
낮은 반품;
}
함수 정렬(요소, 낮음, 높음){
if(낮음<높음){
// 시퀀스를 2개로 분할하여 분할 위치 전후의 시퀀스로 나눕니다. 전자의 시퀀스가 ​​분할 위치보다 작은 값을 갖고, 후자의 시퀀스가 ​​분할 위치보다 큰 값을 갖습니다.
var partitionPos=파티션(요소, 낮음, 높음);
//이전 시퀀스를 계속 재귀적으로 정렬
Sort(요소, 0, partitionPos-1);
//다음 시퀀스를 계속 재귀적으로 정렬
Sort(elements, partitionPos 1, high);
}
}
var 요소 = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('이전: ' 요소);
sort(elements, 0, elements.length-1);
console.log(' 이후: ' 요소);

효율성:

시간 복잡도: 최고: O(nlog2n), 최악: O(n^2), 평균: O(nlog2n).

공간 복잡도: O(nlog2n).

안정성: 불안정합니다.