Java 정렬 알고리즘 요약 병합 정렬

본고는 자바 정렬 알고리즘의 요약 정렬을 실례로 서술한다.여러분에게 참고할 수 있도록 나누어 드리겠습니다.구체적인 분석은 다음과 같다.
병합 조작(merge)은 병합 알고리즘이라고도 하는데 이미 정렬된 두 서열을 하나의 서열로 합친 조작을 가리킨다.빠른 정렬과 유사하게 자바에서 통합된 것을 살펴봅시다.
병합 정렬(Merge)은 두 개 이상의 순서표를 하나의 새로운 순서표로 합친 것이다. 즉, 정렬을 기다리는 서열을 몇 개의 하위 서열로 나누고, 각 하위 서열은 질서정연하다.그리고 나서 질서 서열을 전체 질서 서열로 합친다.
병합 정렬은 병합 조작에 세워진 효과적인 정렬 알고리즘이다.이 알고리즘은 분리법(Divide and Conquer)을 채택한 매우 전형적인 응용 프로그램이다.기존 서열의 하위 서열을 합쳐서 완전히 질서정연한 서열을 얻기;즉, 먼저 각 하위 시퀀스를 질서정연하게 한 다음에 하위 시퀀스 세그먼트 사이를 질서정연하게 합니다.만약 두 개의 질서표를 하나의 질서표로 합치면 2로귀합이라고 부른다.
병합 정렬 알고리즘이 안정적이고 수조는 O(n)의 추가 공간이 필요하며 체인 테이블은 O(log(n))의 추가 공간이 필요하며 시간 복잡도는 O(nlog(n)이다. 알고리즘은 스스로 적응하는 것이 아니라 데이터에 대한 무작위 읽기가 필요하지 않다.
작동 방식:
1. 신청 공간은 크기를 두 개의 정렬 서열의 합으로 하고 이 공간은 통합된 서열을 저장하는 데 쓰인다
2. 두 개의 포인터를 설정하고 첫 번째 위치는 정렬된 두 시퀀스의 시작 위치이다
3. 두 포인터가 가리키는 원소를 비교하고 상대적으로 작은 원소를 선택하여 합병 공간에 넣고 포인터를 다음 위치로 이동한다
4. 포인터가 시퀀스 끝에 도달할 때까지 3단계 반복
5. 다른 시퀀스에 남은 모든 요소를 병합 시퀀스 끝에 직접 복사
코드 구현:

////////////////
public void mergeSort(){
 long[] workSpace = new long[nElems];
 recMergeSort(workSpace,0,nElems-1);
}
private void recMergeSort(long[] workSpace,int lowerBound,int upperBound){
 if(lowerBound == upperBound){
  return;
 }
 else{
  int mid=(lowerBound+upperBound)/2;
  recMergeSort(workSpace, lowerBound, mid);
  recMergeSort(workSpace, mid+1, upperBound);
  merge(workSpace, lowerBound, mid+1, upperBound);
 }
}
private void merge(long[] workSpace,int lowPtr,int highPtr,int upperBound){
 int j = 0;
 int lowerBound = lowPtr;
 int mid = highPtr - 1;
 int n = upperBound-lowerBound+1;
 while(lowPtr<=mid&&highPtr<=upperBound){
  if(theArray[lowPtr]<theArray[highPtr]){
  workSpace[j++]=theArray[lowPtr++];
  }
  else{
  workSpace[j++]=theArray[highPtr++];
  }
 }
 while(lowPtr<=mid){
  workSpace[j++] = theArray[lowPtr++];
 }
 while(highPtr<=upperBound){
  workSpace[j++] = theArray[highPtr++];
 }
 for(j=0;j<n;j++){
  theArray[lowerBound+j]=workSpace[j];
 }
}

병합 정렬은 비교적 안정적인 정렬이다.즉, 같은 원소의 순서는 바뀌지 않는다.레코드 1 (1) 3 (2) 2 (3) 2 (4) 5 (5) (괄호 안에 기록된 키워드) 를 입력할 때 출력되는 1 (1) 2 (3) 2 (2) 5 (5) 의 2 및 2 는 입력 순서입니다.이것은 데이터를 정렬할 때 여러 개의 정보를 포함하고 그 중의 어떤 정보에 따라 정렬해야 하며, 다른 정보는 가능한 한 입력한 순서에 따라 정렬해야 할 때 매우 중요하다.이것도 그것이 빠른 순서보다 우세한 곳이다.
본고에서 기술한 것이 여러분의 자바 프로그램 설계에 도움이 되기를 바랍니다.