파티션 및 스왑 정렬이라고도하는 빠른 정렬. 나누기 및 정복 전략으로 구현 된 빠른 정렬 알고리즘.
이 기사는 주로 JavaScript를 사용하여 내부 아이디어의 빠른 정렬을 구현하는 것에 대해 이야기합니다.
방법 분할 및 처리 :
컴퓨터 과학에서, 부서 및 정복 방법은 다수의 지점 재귀를 기반으로하는 매우 중요한 알고리즘 패러다임입니다. 문자 그대로의 설명은 "나누기 및 정복"이며, 이는 복잡한 문제를 하위 문제의 끝이 간단하고 직접 해결 될 때까지 복잡한 문제를 둘 이상의 동일하거나 유사한 하위 문제로 나누는 것을 의미하며, 원래 문제의 해결책은 하위 문제의 해결책의 합병입니다. (Wikipedia에서 발췌)
빠른 분류 아이디어
배열의 요소를 통치자로 지정하고, 그보다 더 큰 것을 배치하고 요소보다 작은 것을 배치하고, 모든 것이 양수 순서로 배열 될 때까지 반복하십시오.
빠른 분류는 세 단계로 나뉩니다.
벤치 마크 선택 : 데이터 구조 (Pivot)에서 벤치 마크로 요소를 선택하십시오.
파티션 : 참조 요소 값의 크기를 참조하고, 순서가없는 영역을 나누십시오. 참조 요소보다 작은 모든 데이터는 한 간격으로 배치되며 참조 요소보다 큰 모든 데이터는 다른 간격으로 배치됩니다. 파티션 조작이 완료된 후, 참조 요소의 위치는 최종 정렬 후에 위치해야합니다.
재귀 : 1 단계와 2 단계의 알고리즘을 재귀 적으로 호출하여 모든 unordered 간격으로 남은 요소가 하나만 남을 때까지 처음으로 호출합니다.
이제 일반적인 구현 방법에 대해 이야기 해 봅시다 (현장 알고리즘이 사용되지 않음).
함수 QuickSort (ARR) {if (arr.length <= 1) 반환; // 배열 중간에 가장 가까운 숫자 벤치 마크, 홀수 및 숫자 값은 값이 다르지만 그렇게 생각하지 않습니다. 물론, 당신은 첫 번째 또는 마지막 숫자를 벤치 마크로 선택할 수 있으며, 여기에 너무 많은 설명이 없습니다. 여기에는 var pivotindex = math.floor (arr.length/2); var pivot = Ar i = 0; i arr.length; i ++) {console.log ( ' + (i + 1) +'파티션 조작 루프 : // 왼쪽 간격, 참조보다 크고 (arr [i] <pivot) {arr [i]); {right.push (arr [i]); console.log ( 'right :' + ' + (arr [i]))}} // concat 연산자는 왼쪽 간격, 참조 및 오른쪽 간격을 새 배열로 스플릿 한 다음, 모든 uns QuickSort (오른쪽);} var arr = [14, 3, 15, 7, 76, 11]; console.log (QuickSort (ARR));/** 첫 번째 파티션은 왼쪽과 오른쪽에 두 개의 서브 세트로 얻어집니다 [3, 2,] 7 [14, 15, 76, 11];* 왼쪽 서브 세트는 [3, 2]는 모두 획득합니다. 왼쪽 서브 세트 끝의 정렬* 76으로, 오른쪽 서브 세트는 나누어지고 분류되어 [14, 15, 11] 76* 이시기에, 위의 [14, 15, 11]은 위의 [14, 15, 11]으로 분류되어 분할되며 위의 [14, 11]은 [14, 11]으로 분류되며 위의 분류는 위의 분류이며 위의 분류는 나뉘어져 있으며 [14, 11]은 위에 분류됩니다. [14, 11]은 상기로 분할되고 분류된다 [11]은 분할되고 기저 11, 11 [14]로 분류된다.브레이크 포인트 디버깅을 통해 결과를 얻을 수 있습니다.
단점 :
ω (n)의 추가 저장 공간이 필요하며, 이는 병합 분류만큼 나쁘다. 생산 환경에서는 추가 메모리 공간이 필요하며 성능에 영향을 미칩니다.
동시에, 많은 사람들은 위의 것이 진정한 빠른 종류라고 생각합니다. 따라서 아래에서 내장 알고리즘의 빠른 정렬을 권장해야합니다.
현장 알고리즘에 대한 자세한 내용은 Wikipedia를 참조하십시오. 벽 아래에있는 학생들은 바이두와 비슷합니다.
현장
빠른 정렬은 일반적으로 재귀로 구현됩니다. 가장 중요한 것은 분할 분할 기능으로 배열을 두 부분으로 나누고 하나는 피벗보다 작고 다른 하나는 피벗보다 큽니다. 특정 원칙은 위에서 언급되어 있습니다
함수 QuickSort (arr) {// swap 함수 스왑 (ARR, a, b) {var temp = arr [a]; arr [a] = arr [b]; arr [b] = temp;} // partition function partition (arr, 왼쪽, 오른쪽) {/*** 최종 피벗 스토리지 위치를 알지 못합니다. = ARR [오른쪽];/*** 피벗보다 작은 요소를 저장할 때 이전 요소 옆에 있습니다. 그렇지 않으면 갭에 저장된 요소가 피벗보다 클 수 있습니다. */var storeIndex = left; for (var i = 왼쪽; i <오른쪽; i ++) {if (arr [i] <pivot) {/*** 배열을 가로 지르고 피벗보다 작은 요소를 찾으십시오 (피봇보다 큰 요소가 건너 뜁니다. 교환*/swap (arr, storindex, i); storeIndex ++;}} // 마지막으로 : 마지막 : swap pivot을 storeIndex로 바꾸고, 최종 올바른 위치 스왑 (arr, 오른쪽, StoreIndex)에 벤치 마크 요소를 배치하십시오. 1); Sort (Arr, StoreIndex + 1, 오른쪽);} Sort (Arr, 0, Ar파티션 최적화
여기에 신중한 학생들은 다른 벤치 마크를 선택할 때 성능이 다른 성능이 있는지 물어볼 수 있습니다. 대답은 그렇습니다. 그러나 저는 프론트 엔드 사람이고 알고리즘에 대해 많이 알지 못하기 때문에이 구덩이는 강력한 사람들에게 채워집니다.
복잡성
빠른 정렬은 가장 빠른 정렬 알고리즘이며 시간 복잡성은 O (log n)입니다.
평균 상황에서 N 항목의 순서는 ο (n log n) 비교가 필요합니다. 최악의 경우 ο (N2) 비교가 필요합니다.
https://github.com/lyz0106/
위의 것은 편집자가 소개 한 자바 스크립트 구현의 빠른 정렬 방법입니다. 모든 사람에게 도움이되기를 바랍니다. 궁금한 점이 있으면 메시지를 남겨주세요. 편집자는 제 시간에 답장을 드릴 것입니다. Wulin Network 웹 사이트를 지원해 주셔서 대단히 감사합니다!