A의 끝에 B를 위한 충분한 공간이 있는 두 개의 정렬된 배열 A와 B가 주어지면 B를 A로 병합하고 정렬하는 메서드를 작성합니다.
이 질문을 받은 후 가장 직접적인 아이디어는 A와 B의 요소를 비교하고 A와 B의 모든 요소가 순회될 때까지 순서대로 배열에 삽입하는 것입니다. 하지만 이렇게 하면 단점이 있습니다. 요소의 삽입 위치가 배열 A의 앞에 있으면 원래 배열을 뒤로 이동해야 합니다. 이로 인해 오버헤드가 추가됩니다. 그러나 다른 방법을 사용하여 배열 A의 끝에 요소를 삽입할 수 있습니다. 이렇게 하면 요소가 움직이지 않게 됩니다! 코드는 다음과 같습니다:
다음과 같이 코드 코드를 복사합니다. /*
* lastA: lastB의 실제 요소 개수 mergeIndex는 새 배열의 실제 공간 크기입니다.
*/
공개 정적 무효 mergeOrder(int[] a, int[] b, int lastA, int lastB) {
int indexA = lastA - 1;
int indexB = lastB - 1;
int mergeIndex = lastA + lastB - 1;
while (indexA >= 0 && indexB >= 0) {
if (a[indexA] > b[indexB]) {
a[mergeIndex] = a[indexA];
병합 인덱스 --;
인덱스A --;
} 또 다른 {
a[mergeIndex] = b[indexB];
병합 인덱스 --;
인덱스B --;
}
}
동안 (indexB >= 0) {
a[mergeIndex] = b[indexB];
병합 인덱스 --;
인덱스B --;
}
}