병합 (병합) 정렬 알고리즘 원리 와 구현
분할 통치하 다
알고리즘 원리:
병합 정렬 법 은 두 개의 (또는 두 개 이상) 질서 표를 하나의 새로운 질서 표 로 합 치 는 것 이다. 즉, 정렬 대기 서열 을 몇 개의 하위 서열 로 나 누고 모든 하위 서열 은 질서 가 있다.그리고 질서 있 는 하위 서열 을 전체 질서 있 는 서열 로 합 친다.기 존 서열 의 하위 서열 을 합쳐서 완전히 질서 있 는 서열 을 얻는다.즉, 모든 하위 서열 을 질서 있 게 한 다음 에 하위 서열 을 질서 있 게 하 는 것 이다.두 개의 질서 표를 하나 로 합치 면
시공 복잡 도:
시간 복잡 도 O (nlogn)
공간 복잡 도 O (n)
구체 적 인 구현 코드 (C):
/*
MergeSort. Code
*/
#include <iostream>
using namespace std;
void merge(int A[], int low, int mid, int high)
{
int len_left = mid - low + 1;
int len_right = high - mid;
int *LEFT = new int[len_left];
int *RIGHT = new int[len_right];
for (int i = 0; i < len_left; ++ i)
LEFT[i] = A[low+i];
for (int i = 0; i < len_right; ++ i)
RIGHT[i] = A[mid+1+i];
int m = 0;
int n = 0;
for (int i = low; i <= high; ++ i)
{
if (m<len_left && n < len_right)
{
A[i] = LEFT[m]<RIGHT[n]?LEFT[m++]:RIGHT[n++];
}
else
{
if (m<len_left)
{
A[i] = LEFT[m++];
}
if (n<len_right)
{
A[i] = RIGHT[n++];
}
}
}
delete [] LEFT;
delete [] RIGHT;
};
void mergesort(int A[], int low, int high)
{
if (low < high)
{
int mid = (low+high) >> 1;
mergesort(A, low, mid);
mergesort(A, mid+1, high);
merge(A, low, mid, high);
}
};
int main()
{
int T,n,a[1005];
cin >> T;
while (T --)
{
cin >> n;
for (int i = 0; i < n; ++ i)
cin >> a[i];
mergesort(a, 0, n-1);
for (int i = 0; i < n-1; ++ i)
cout << a[i] << " ";
cout << a[n-1] << endl;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Docker를 사용한 React 및 .NET Core 6.0 샘플 프로젝트 - 1부이 기사에서는 Entity Framework Core Code First 접근 방식을 사용하는 ASP.NET Core 6.0 WEP API의 CRUD(만들기, 읽기, 업데이트 및 삭제) 작업에 대해 설명합니다. 웹 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
