C 언어 통합 정렬 및 인 스 턴 스 코드

병합 정렬 도 병합 정렬 이 라 고 하 는데 그 알고리즘 사상 은 정렬 대기 서열 을 두 부분 으로 나 누고 순서대로 분 리 된 두 부분 에 대해 다시 병합 정렬 을 사용 한 다음 에 이 를 합병 하 는 것 이다.알고리즘 사상 에서 만 병합 순 서 를 이해 하면 추상 적 이 라 고 느 낄 수 있 습 니 다.그 다음 에 서열 A[0],A[l]...................................................................
작업 절 차 는 다음 과 같다.
(1)진행 할 정렬 순 서 를 좌우 두 부분 으로 나 누고 정렬 을 진행 할 시퀀스 의 시작 요소 아래 에 first,마지막 요소 의 아래 에 last 로 표시 하면 좌우 두 부분 사이 의 임계 점 아래 에 mid=(first+last)/2 를 표시 합 니 다.이 두 부분 은 각각 A[first..mid]와 A[mid+1..last]입 니 다.
(2)위 에서 분 리 된 두 부분의 서열 을 계속 절차(1)에 따라 구간 길이 가 1 일 때 까지 계속 구분한다.
(3)구분 이 끝 난 후의 서열 을 병합 하여 정렬 합 니 다.정렬 방법 은 n 개의 키 서열 을 두 번 합 친 다음 에 n/2 또는 n/2+l 개의 두 요 소 를 포함 한 하위 서열 을 얻 은 다음 에 얻 은 하위 서열 을 합 친 다음 에 n 의 길이 가 n 인 질서 있 는 서열 을 얻 을 때 까지 합 친 것 입 니 다.
다음은 코드 를 통 해 병합 정렬 을 어떻게 실현 하 는 지 보 겠 습 니 다.

#include <stdio.h>
#include <stdlib.h>
#define N 7
void merge(int arr[], int low, int mid, int high){
 int i, k;
 int *tmp = (int *)malloc((high-low+1)*sizeof(int));
 //    ，       
 int left_low = low;
 int left_high = mid;
 int right_low = mid + 1;
 int right_high = high;
 for(k=0; left_low<=left_high && right_low<=right_high; k++){ //             
  if(arr[left_low]<=arr[right_low]){
   tmp[k] = arr[left_low++];
  }else{
   tmp[k] = arr[right_low++];
  }
 }
 if(left_low <= left_high){ //         ，             
 //memcpy(tmp+k, arr+left_low, (left_high-left_low+l)*sizeof(int));
 for(i=left_low;i<=left_high;i++)
  tmp[k++] = arr[i];
 }
 if(right_low <= right_high){
 //         ，             
 //memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int));
  for(i=right_low; i<=right_high; i++)
   tmp[k++] = arr[i];
 }
 for(i=0; i<high-low+1; i++)
  arr[low+i] = tmp[i];
 free(tmp);
 return;
}
void merge_sort(int arr[], unsigned int first, unsigned int last){
 int mid = 0;
 if(first<last){
  mid = (first+last)/2; /*        */
  /*mid = first/2 + last/2;*/
  //mid = (first & last) + ((first ^ last) >> 1);
  merge_sort(arr, first, mid);
  merge_sort(arr, mid+1,last);
  merge(arr,first,mid,last);
 }
 return;
}
int main(){
 int i;
 int a[N]={32,12,56,78,76,45,36};
 printf ("    
");
 for(i=0;i<N;i++)
  printf("%d\t",a[i]);
 merge_sort(a,0,N-1); //   
 printf ("
     
");
 for(i=0;i<N;i++)
  printf("%d\t",a[i]); printf("
");
 system("pause");
 return 0;
}

실행 결과:
정렬 전
32    12    56    78    76    45    36
정렬 후
12    32    36    45    56    76    78
위의 운행 결 과 를 분석 하고 정렬 을 통 해 주어진 서열 에 대한 정렬 작업 을 성공 적 으로 실현 했다.다음은 그림 을 통 해 정렬 의 구체 적 인 작업 절 차 를 알 아 보 겠 습 니 다.
다음 그림 에서 정렬 할 서열 을 하나의 요소 로 나 눌 때 까지 분해 한 다음 에 두 개의 병합 을 한다.최종 적 으로 하나의 요소 로 분해 되 기 때문에 합병 할 때 작은 수 를 앞 에 놓 고 큰 수 를 뒤에 놓 아 질서 있 는 서열 을 얻 을 수 있 습 니 다.그 다음 에 두 개의 연 결 된 질서 있 는 서열 에 대해 순 서 를 매 긴 다.먼저 질서 있 는 서열 중의 첫 번 째 요 소 를 비교 하고 작은 요 소 를 임시 배열 에 넣 은 다음 에 작은 요소 가 있 는 배열 의 다음 요 소 를 다른 배열 의 작은 요소 와 비교 한 다음 에 작은 원 소 를 임시 배열 에 넣 고 순서대로 진행한다.두 배열 의 모든 요 소 를 임시 배열 에 넣 을 때 까지 마지막 으로 임시 배열 의 요 소 를 원시 배열 의 대응 위치 에 넣 습 니 다.

이상 은 합병 정렬 에 대한 상세 한 설명 입 니 다.도움 이 되 기 를 바 랍 니 다.