알고리즘 정리-비귀속 병합 정렬
자주 사용하는 병합 정렬은 병합 정렬 방식을 사용하여 정렬 서열을 한 층 한 층 반으로 나누어 한 층의 정렬을 완성한 후에 다시 한 층 위로 되돌려 처리하는 것이다.
사실 병합 정렬은 다음과 같은 대략적인 절차에서 비귀속 방법을 사용할 수도 있습니다.
1. 순환하여 각 구역을 구분하고 각 구역은 1부터 시작한다.
2. 인접한 두 개의 구역을 병합 정렬하는 방법에 따라 버퍼에 넣는다.
3. 버퍼에서 원래 구역의 위치로 복사하기;
4. 모든 구역이 통합될 때까지 2로 돌아가기;
5. 1로 돌아가면 세그먼트가 수조의 길이보다 클 때까지 세그먼트가 2배로 커진다.
/**
* param
* arr: ， len
*
*/
void merge_sort(int* arr, int len){
int * buff = new int[len]; //buffer
//
for(int i = 1 ; i < len ; i *= 2){
//
for(int j = 0 , k = i ; k < len ; j += 2*i, k += 2*i ){
int buffIndex = 0 ; //buffer index
//
for(int m = j , n = k ; ; ){
if(arr[m] <= arr[n]){
buff[buffIndex++] = arr[m++];
if(m >= k){ // copy
while(n < k + i && n < len){
buff[buffIndex++] = arr[n++];
}
break;
}
}else{
buff[buffIndex++] = arr[n++];
if(n >= k+i || n >= len){ // copy
while(m < k ){
buff[buffIndex++] = arr[m++];
}
break;
}
}
}
// buffer copy
for(int l = 0 ; l < 2*i && j + l < len; l++){
arr[j+l] = buff[l];
}
}
}
delete [] buff;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Java 정렬 알고리즘 요약 병합 정렬병합 조작(merge)은 병합 알고리즘이라고도 하는데 이미 정렬된 두 서열을 하나의 서열로 합친 조작을 가리킨다.빠른 정렬과 유사하게 자바에서 통합된 것을 살펴봅시다. 병합 정렬(Merge)은 두 개 이상의 순서표를...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
