JS_javascript 기술에서 무작위 빠른 정렬을 구현하기 위한 예제 코드

알고리즘의 평균 시간 복잡도는 O(nlogn)입니다. 그러나 입력이 정렬된 배열이거나 거의 정렬된 입력인 경우 시간 복잡도는 O(n^2)입니다. 이 문제를 해결하고 평균 시간 복잡도가 O(nlogn)임을 보장하기 위해 이 방법에서는 요소의 순서를 무작위 순서로 변경하는 것이 유일한 목적인 전처리 단계를 도입하는 것입니다. 이 전처리 단계는 O(n) 시간 내에 실행될 수 있습니다. 동일한 효과를 얻을 수 있는 또 다른 간단한 방법은 알고리즘에 무작위 요소를 도입하는 것입니다. 이는 분할 요소의 피벗을 무작위로 선택하여 달성할 수 있습니다. 피벗을 무작위로 선택하면 입력 요소의 모든 순열이 동일할 가능성이 있는 지점까지 단계가 완화됩니다. 이 단계는 원래의 퀵 정렬을 수정하기 위해 도입된 것으로, 아래와 같은 무작위 퀵 정렬을 얻을 수 있습니다. 새로운 알고리즘은 [low...high] 간격에서 인덱스 v를 무작위로 선택하고 A[v]와 A[low]를 교환한 다음 원래의 빠른 정렬 알고리즘에 따라 계속됩니다. 여기서,parseInt(Math.random()*(high-low 1) low)는 낮음과 높음 사이의 숫자를 반환합니다.

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

　
/*****************************************
알고리즘: 분할
입력: 배열 A[low...high]
출력:
1. 필요한 경우 위에서 설명한 대로 재배열된 배열 A를 출력합니다.
2. 요소 A의 새 위치 w를 나눕니다. >*****************************************/
함수 분할(배열, low, high) {
　var i = low;
　var x = array[low];
　for(var j = low 1; j <= high; j ) {
if(array[j] <= x) {
i ;
if(i != j) {
var temp = array[i];
array[i] = 배열[ j];
배열[j] = 임시;
}
}
}
임시 = 배열[low];
배열[low] = 배열[i] ;
array[i] = temp;
return i;
}
/*****************************************
알고리즘: rquicksort
입력: A [0...n-1]
출력: 내림차순이 아닌 배열 A[0...n-1]
배열 rquicksort(A, 0, n-1);
* *** **************************************/
function rquicksort(array, low, high) {
if( 낮음 < 높음) {
　/******분할 요소의 피벗을 무작위로 지정*****/
　var v =parseInt(Math.random()*(high-low 1) low);
　var tmp = array[낮음] ;
array[low] = 배열[v];
array[v] = tmp;
/******분할 요소의 피벗을 무작위로 지정*****/
var w = 분할(배열, 낮음, 높음);
rquicksort(array, low, w -1);
rquicksort(array, w 1, high)
return array;
}
}
var array = [33, 22, 11 , 88, 23, 32];
array = rquicksort(array, 0, array.length-1);
console.log(array);