먼저 두 개의 정렬된 시퀀스를 병합하는 방법을 고려하십시오. 이는 매우 간단합니다. 두 시퀀스의 첫 번째 숫자를 비교하여 더 작은 숫자를 먼저 취한 후 해당 시퀀스의 숫자를 삭제하면 됩니다. 그런 다음 열 중 하나가 비어 있으면 다른 열의 데이터를 하나씩 꺼내십시오.
다음과 같이 코드 코드를 복사합니다 .
코드 보기
//순서 있는 배열 a[] 및 b[]를 c[]로 병합
void MemeryArray(int a[], int n, int b[], int m, int c[])
{
int i, j, k;
나는 = j = k = 0;
동안(i < n && j < m)
{
if (a[i] < b[j])
c[k++] = a[i++];
또 다른
c[k++] = b[j++];
}
동안 (i < n)
c[k++] = a[i++];
동안(j<m)
c[k++] = b[j++];
}
정렬된 시퀀스를 병합하는 효율성은 상대적으로 높고 O(n)에 도달할 수 있음을 알 수 있습니다.
위의 정렬된 시퀀스 병합 문제를 해결한 후 병합 정렬을 살펴보겠습니다. 기본 아이디어는 배열을 두 그룹 A와 B로 나누는 것입니다. 이 두 그룹의 데이터가 모두 정렬되어 있으면 쉽게 이 두 세트를 사용할 수 있습니다. 데이터가 정렬됩니다. 이 두 그룹의 데이터를 순서대로 유지하는 방법은 무엇입니까?
그룹 A와 B는 두 그룹으로 나눌 수 있습니다. 비유하자면, 분리된 그룹에 하나의 데이터만 있는 경우 그룹이 순서에 도달한 것으로 간주하고 인접한 두 그룹을 병합할 수 있습니다. 이런 방식으로 병합 정렬은 먼저 배열을 재귀적으로 분해한 다음 배열을 병합하여 완료됩니다.
다음과 같이 코드 코드를 복사합니다 .
코드 보기
//두 개의 정렬된 시퀀스 a[first...mid] 및 a[mid...last]를 병합합니다.
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = 첫 번째, j = mid + 1;
int m = 중간, n = 마지막;
정수 k = 0;
동안 (i <= m && j <= n)
{
if (a[i] <= a[j])
온도[k++] = a[i++];
또 다른
온도[k++] = a[j++];
}
동안 (i <= m)
온도[k++] = a[i++];
동안 (j <= n)
온도[k++] = a[j++];
for (i = 0; i < k; i++)
a[첫 번째 + i] = 온도[i];
}
void mergesort(int a[], int 먼저, int 마지막, int temp[])
{
if(처음 <마지막)
{
int mid = (첫 번째 + 마지막) / 2;
mergesort(a, first, mid, temp); //왼쪽이 정렬됩니다.
mergesort(a, mid + 1, last, temp); //오른쪽이 정렬됩니다.
mergearray(a, first, mid, last, temp); //순서가 지정된 두 배열을 병합합니다.
}
}
bool MergeSort(int a[], int n)
{
int *p = 새로운 int[n];
if (p == NULL)
거짓을 반환;
mergesort(a, 0, n - 1, p);
삭제[] p;
사실을 반환;
}
병합 정렬의 효율성은 상대적으로 높습니다. 시퀀스의 길이를 N이라고 가정합니다. 시퀀스를 십진 시퀀스로 나누는 데는 logN 단계가 필요합니다. 각 단계는 정렬된 시퀀스를 병합하는 프로세스입니다. N)이므로 합계는 O(N*logN)입니다. 병합 정렬은 매번 인접한 데이터에 대해 동작하기 때문에 O(N*logN)의 병합 정렬(퀵 정렬, 병합 정렬, 힐 정렬, 힙 정렬)의 여러 정렬 방법도 상대적으로 효율적입니다.