소개
리버스로 정렬 된 입력에 대한 Mergesort의 복잡성은 O (n^2) 이며이 상황에 대한 Mergesort를 최적화하여 Timsort가 생성됩니다. 평균 복잡성은 n*o (log n)이고, 가장 좋은 경우는 O (n)이고 최악의 경우는 n*o (log n)입니다. 그리고 Timsort는 안정성 정렬입니다. 아이디어는 먼저 정렬 된 열을 분할 한 다음 Mergesort 단계와 동일하게 보이는 파티션을 병합하는 것입니다. 그러나 리버스 및 대규모 데이터에 대한 일부 최적화가 있습니다.
병합 분류의 최적화 아이디어
병합 분류를위한 몇 가지 최적화 방법이 있습니다.
빠른 정렬과 마찬가지로 재귀 통화를 피하기 위해 삽입 정렬 또는 작은 배열의 정렬을 선택할 수 있습니다.
merge ()가 호출되기 전에 [중간]가 [중간+1]보다 작거나 같은지 여부를 결정할 수 있습니다. 그렇다면 병합 할 필요가 없으며 배열이 이미 주문되었습니다. 그 이유는 매우 간단합니다. 두 개의 서브 어레이가 이미 주문되었으므로 [중간]는 첫 번째 서브 어레이의 최대 값이고 [중간+1]은 두 번째 서브 어레이의 최소값입니다. A [Mid] <= a [Mid+1] 인 경우 배열은 전체적으로 주문됩니다.
보조 배열에 요소를 복사 할 시간을 절약하기 위해 원래 배열 및 보조 배열의 역할을 재귀 호출의 각 레벨에서 교체 할 수 있습니다.
merge () 메소드의 병합 프로세스는 I와 J가 경계를 넘어 섰는 지, 즉 가장자리의 절반이 소비되었는지 여부를 결정해야합니다. 측면의 절반이 소진되었는지 여부를 감지하는 코드를 제거하는 또 다른 방법. 구체적인 단계는 배열의 후반부를 내림차순으로 aux []에 복사 한 다음 양쪽 끝에서 병합하는 것입니다. 배열 {1,2,3} 및 {2,3,5}의 경우, 첫 번째 서브 어레이는 평소와 같이 복사되고 두 번째는 뒤에서 전면으로 복사되고 Aux []의 최종 요소는 {1,2,3,5,3,2}입니다. 이 방법의 단점은 병합 분류가 불안정한 정렬이된다는 것입니다. 코드 구현은 다음과 같습니다.
void merge (int [] a, int lo, int mid, int hi, int [] aux) {for (int k = lo; k <= mid; k ++) {aux [k] = a [k];} for (int k = mid+1; k <= hi; k ++) {aux [k] = a [hi -k+mid+1];} int i = lo, j = hy; // 두 끝에서 중간으로 (int k = lo; k <= hi; k ++) if (aux [i] <= aux [j]) a [k] = aux [i ++]; else a [k] = aux [j-];}Timsort의 단계
분할
분할의 아이디어는 배열을 한 번 스캔하고 연속적인 양의 시퀀스를 사용하는 것입니다 (오름차순 순서로 정렬 된 경우 양의 순서는 오름차순 시퀀스입니다) 또는 [정렬 알고리즘의 안정성을 보장하기 위해) (실행). 리버스 시퀀스 인 경우 파티션의 요소를 반전하십시오. 예를 들어
1, 2, 3, 6, 4, 5, 8, 6, 4 파티션 결과는 다음과 같습니다.
[1,2,3,6], [4,5,8], [6,4]
그런 다음 리버스 시퀀스를 반전하십시오
[1,2,3,6], [4,5,8], [4,6]
병합
예를 들어, 파티션의 길이는 10000, 10, 1000, 10, 10 및 10 인 경우를 고려하십시오. 물론 우리는 먼저 10 10으로 20, 20 및 1000을 1020으로 병합하기를 희망합니다. 왼쪽에서 오른쪽으로 병합하면 배열 10000과 작은 숫자의 조합을 사용하여 너무 비쌉니다. 따라서 우리는 병합 순서를 최적화하기 위해 전략을 사용할 수 있습니다.
예
Java에서 ComparableTimsort.sort ()를 예로 들어 런 스택을 사용하여 병합되어야하는지 여부를 결정합니다.
if (nremaining <min_merge) {int initrunlen = countrunandmakeascending (a, lo, hi); BinarySort (a, lo, hi, lo + initrunlen); 반품; }min_merge (32)보다 적게 정렬하고 분할 후 바이너리 삽입으로 직접 정렬하십시오.
int minrun = minrunlength (nremaining); {// 다음 파티션의 시작 위치를 찾아서 리버스 시퀀스 int runlen = countrunandmakeascending (a, lo, hi)을 뒤집습니다. // 런 스택의 실행이 Minrun보다 더 큽니다. 현재 파티션이 너무 작은 경우 뒷면에서 요소를 꺼내 (runlen <minrun) {int force = nremaining <= minrun? Nremaining : Minrun; BinarySort (a, lo, lo + force, lo + runlen); runlen = 힘; } // 런 스택으로 실행됩니다. ts.Pushrun (lo, runlen); // 병합되어야하는지 판단합니다. 나는 스택의 상단에서 시작하여 병합 될 수 없다는 것을 알고 있습니다. runlen [i -3]> runlen [i -2] + runlen [i -1] // 2. runlen [i -2]> runlen [i -1] ts.mergecollapse (); lo += runlen; nremaining- = runlen; } while (nremaining! = 0); // 나머지 실행을 완료하기 위해 모든 정렬 정렬 assert asert lo == hi; // 나머지 실행을 병합 ts.mergeforceCollapse (); Assert ts.stacksize == 1;더 중요한 기능을보고 있습니다
/ *** 마지막 2 런의 길이가 이전의 길이보다 더 길어지면 중간 위치에서의 달리기를 사용하고 전면 및 후면 길이가 짧은 런을 사용하여 병합*마지막 2 런의 길이가 이전보다 짧은 후에 추가 된 다음 두 실행*/ private void mergecollapse () {while (stacksize> 1) {int n = int n = stacks -2; if (n> 0 && runlen [n-1] <= runlen [n] + runlen [n + 1]) {if (runlen [n-1] <runlen [n + 1]) n-; 합병 (n); } else if (runlen [n] <= runlen [n + 1]) {mergeat (n); } else {break; // 불변이 확립되었습니다}}