병합은 2 개 (또는 2 개 이상)의 정렬 된 테이블을 새로운 주문 테이블로 병합하는 것입니다. 그런 다음 순서 대상 후속을 전체 순서 시퀀스로 결합합니다.
병합 정렬은 병합 작업을 기반으로 한 효과적인 정렬 알고리즘입니다. 이 알고리즘은 분열 및 정복의 매우 전형적인 적용입니다. 순서 대상 후속 시퀀스를 병합하여 완전히 순서가 서열을 얻은 다음 각 하단 세그먼트를 순서로 만듭니다. 정렬 된 두 테이블이 하나의 주문 테이블로 병합되면 2 방향 병합이라고합니다.
Merge 정렬 알고리즘은 O (N)에 대한 추가 공간이 필요하며 (Log (N))에 대한 추가 공간이 필요하며 (NLOG (N)) 적응하지 않고 데이터가 필요하지 않습니다.
작동 방식 :
1. 크기가 두 개의 정렬 된 시퀀스의 합이되도록 공간을 적용하고 결합 된 시퀀스를 저장하는 데 사용됩니다.
2. 두 개의 포인터를 설정하면 초기 위치는 각각 두 개의 분류 된 시퀀스의 시작 위치입니다.
3. 두 개의 포인터로 가리키는 요소를 비교하고 비교적 작은 요소를 선택하고 병합 공간에 넣고 포인터를 다음 위치로 이동하십시오.
4. 포인터가 시퀀스의 끝에 도달 할 때까지 3 단계를 반복합니다.
5. 다른 시퀀스의 나머지 모든 요소를 병합 시퀀스의 끝에 직접 복사합니다.
코드를 실행하십시오
코드 사본은 다음과 같습니다.
패키지 com.zc.manythread;
java.util.random import;
/**
* 주문
* @author 나는
*
*/
공개 클래스 mergesort {
public static void mergesort (int [] data) {
정렬 (data, 0, data.length -1);
}
public static void sort (int [] data, int left, int right) {
if (왼쪽> = 오른쪽)
반품;
// 중간 인덱스를 찾습니다
int center = (왼쪽 + 오른쪽) / 2;
// 왼쪽 배열의 재귀
정렬 (데이터, 왼쪽, 중앙);
// 올바른 배열을 재귀합니다
정렬 (데이터, 센터 + 1, 오른쪽);
// 병합
병합 (데이터, 왼쪽, 중앙, 오른쪽);
인쇄 (데이터);
}
/**
* 두 배열을 병합하고 처음 두 배열을 순서대로 병합하고 병합 후에도 여전히 순서
*
* @param 데이터
* 배열 객체
* @param이 떠났습니다
* 왼쪽 배열의 첫 번째 요소의 색인
* @param 센터
* 왼쪽 배열의 마지막 요소 인덱스 인덱스 중심+1은 오른쪽 배열의 첫 번째 요소의 인덱스입니다.
* @param 오른쪽
* 오른쪽 배열의 마지막 요소의 색인
*/
public static void merge (int [] data, int left, int center, int right) {
// 임시 배열
int [] tmparr = new int [data.length];
// 오른쪽 배열의 첫 번째 요소의 색인
int mid = center + 1;
// 세 번째 임시 배열의 색인을 기록하십시오
int third = 왼쪽;
// 왼쪽 배열의 첫 번째 요소의 색인을 캐시
int tmp = 왼쪽;
while (왼쪽 <= center && mid <= right) {
// 두 배열에서 가장 작은 것을 꺼내 임시 배열에 넣습니다.
if (data [left] <= data [mid]) {
tmparr [Third ++] = 데이터 [왼쪽 ++];
} 또 다른 {
tmparr [Third ++] = 데이터 [MID ++];
}
}
// 나머지 부품을 임시 배열에 차례로 넣습니다 (실제로, 두 중 하나만 실행됩니다)
while (mid <= right) {
tmparr [Third ++] = 데이터 [MID ++];
}
while (왼쪽 <= 센터) {
tmparr [Third ++] = 데이터 [왼쪽 ++];
}
// 임시 배열의 내용을 원래 배열로 복사합니다.
// (원래 왼쪽 오른쪽 범위의 내용은 원래 배열로 다시 복사됩니다)
while (tmp <= right) {
데이터 [tmp] = tmparr [tmp ++];
}
}
public static void print (int [] data) {
for (int i = 0; i <data.length; i ++) {
System.out.print (데이터 [i] + "/t");
}
System.out.println ();
}
/**
* 임의의 배열을 생성합니다
* @param 수
* @반품
*/
private static int [] createate (int count) {
int [] data = new int [count];
랜덤 rand = 새로운 랜덤 ();
부울 [] bool = 새로운 부울 [100];
int num = 0;
for (int i = 0; i <count; i ++) {
하다 {
// 생성 된 숫자가 동일하면 계속 루프
num = rand.nextint (100);
} while (bool [num]);
bool [num] = true;
데이터 [i] = num;
}
반환 데이터;
}
public static void main (String [] args) {
int [] data = createate (10);
인쇄 (데이터);
Mergesort (데이터);
System.out.println ( "정렬 된 배열 :");
인쇄 (데이터);
}
}
실행 결과 :
위의 것은이 기사에 관한 모든 것입니다. 나는 당신이 그것을 좋아할 수 있기를 바랍니다.