Merge Sort는 병합 작업을 기반으로 한 효과적인 정렬 알고리즘입니다. 이 알고리즘은 분열 및 정복의 매우 전형적인 적용입니다.
병합 정렬 방법은 2 개 (또는 2 개 이상)의 정렬 된 테이블을 새로운 주문 테이블로 병합하는 것입니다. 그런 다음 순서 대상 후속을 전체 순서 시퀀스로 결합합니다.
병합 정렬은 병합 작업을 기반으로 한 효과적인 정렬 알고리즘입니다. 이 알고리즘은 분열 및 정복의 매우 전형적인 적용입니다. 순서 대상 후속 시퀀스를 병합하여 완전히 순서가 서열을 얻은 다음 각 하단 세그먼트를 순서로 만듭니다. 정렬 된 두 테이블이 하나의 주문 테이블로 병합되면 2 방향 병합이라고합니다.
병합 작업 프로세스는 다음과 같습니다.
1. 크기가 두 개의 정렬 된 시퀀스의 합이되도록 공간을 적용하고 병합 된 시퀀스를 저장하는 데 사용됩니다.
2. 두 개의 포인터 설정, 초기 위치는 각각 두 개의 분류 된 시퀀스의 시작 위치입니다.
3. 두 개의 포인터로 가리키는 요소를 비교하고 비교적 작은 요소를 선택하고 병합 공간에 넣고 포인터를 다음 위치로 이동하십시오.
4. 포인터가 시퀀스의 끝에 도달 할 때까지 3 단계를 반복합니다.
5. 다른 시퀀스의 나머지 요소를 병합 시퀀스의 끝에 직접 복사하십시오.
Example 1:
코드 사본은 다음과 같습니다.
/**
* 병합 알고리즘으로도 알려진 병합은 두 개의 정렬 된 시퀀스를 하나의 시퀀스로 결합하는 작업을 나타냅니다.
* 병합 정렬 알고리즘은 병합 작업에 따라 다릅니다.
*
* 병합 작업 프로세스는 다음과 같습니다.
*
* 1. 크기가 두 개의 정렬 된 시퀀스의 합이되도록 공간에 적용되며, 병합 된 시퀀스를 저장하는 데 사용됩니다.
* 2. 두 개의 포인터 설정, 초기 위치는 각각 두 개의 분류 된 시퀀스의 시작 위치입니다.
* 3. 두 포인터가 가리키는 요소를 비교하고 비교적 작은 요소를 선택하고 병합 공간에 넣고 포인터를 다음 위치로 이동하십시오.
* 4. 포인터가 시퀀스의 끝에 도달 할 때까지 3 단계를 반복합니다.
* 5. 다른 시퀀스의 나머지 요소를 병합 시퀀스의 끝에 직접 복사하십시오.
*
*/
함수 mergesort (항목) {
if (items.length <2) {
반품 항목;
}
var middle = math.floor (항목 .length / 2),
왼쪽 = 항목 .slice (0, 중간),
right = items.slice (중간),
params = merge (mergesort (왼쪽), mergesort (오른쪽));
params.unshift (0, items.length);
items.splice.apply (항목, 매개 변수);
반품 항목;
함수 병합 (왼쪽, 오른쪽) {
var result = [],
il = 0,
ir = 0;
while (il <left.length && ir <right.length) {
if (왼쪽 [il] <오른쪽 [ir]) {
result.push (왼쪽 [il ++]);
} 또 다른 {
result.push (오른쪽 [ir ++]);
}
}
return result.concat (left.slice (il)) .concat (right.slice (ir));
}
}
// 시험
var arr = [2, 1, 3, 12, 5, 66, 23, 87, 15, 32];
Mergesort (ARR);
Example 2:
코드 사본은 다음과 같습니다.
<script type = "text/javaScript">
//document.write("------------------------------------- --------------------------------------------------------- ---------------------------------);
// var array = new Array (12, 25, 32, 16, 18, 27, 59, 69, 36);
var count = 0;
// 정렬 메소드를 호출하여 정렬합니다
// msort (배열, 배열, 0, array.length -1);
// 소스 소스 배열
// 대상 배열이 있습니다
// start 첨자
// TARGET 첨자
함수 msort (소스, dest, s, t) {
var result = "";
var m; // 중간 값을 취합니다
var dest2 = new Array ();
if (s == t) {
dest [s] = 출처 [s];
}
또 다른 {
m = math.floor ((s + t) / 2);
MSORT (Source, Dest2, S, M);
msort (소스, dest2, m+1, t);
병합 (dest2, dest, s, m, t);
/* 출력 결과*/
결과 += "<br /> 스레드" +++ count +"패스 순서의 결과는 다음과 같습니다.";
for (var n = 0; n <dest.length; n ++) {
결과 + = 배열 [n] + ",";
}
/* 출력 결과가 끝납니다*/
}
반환 결과;
}
/* 출력 결과가 끝납니다*/
// 두 개의 배열이 작은 것에서 큰 것부터 순서대로 융합되었습니다
// 원래 배열 소스
// DEST 정렬 배열
// STHE 첫 번째 첨자
// 두 번째 배열의 다음 테이블
// ntotal 길이
함수 병합 (Source, Dest, S, M, N) {
for (var j = m+1, k = s; j <= n && s <= m; k ++) {
if (source [s] <source [j]) {
dest [k] = 소스 [s ++];
}
또 다른 {
dest [k] = 소스 [j ++];
}
}
// 나머지 순서대로 배열을 목적지 끝에 추가합니다.
if (s <= m) {
for (var l = 0; l <= m -s; l ++) {
dest [k + l] = 소스 [S + L];
}
}
if (j <= n) {
for (var l = 0; l <= n -j; l ++) {
dest [k + l] = 소스 [j + l];
}
}
}
//document.write("<BR /> <br /> ")
</스크립트>