[데이터 구조] - 내부 정렬 (병합 정렬)

내부 정렬 - 병합 정렬
  • 앞 에 써 주세요
  • 1. 헤더 파일 및 형식 정의
  • 2. 함수 성명
  • 3. 기본 조작
  • 3.1 병합
  • 3.2 주요 과정
  • 3.3 출력
  • 4. main 함수
  • 5. 소결
  • 앞 에 쓰다
    [설명] 다음 코드 는 최종 적 으로 증가 서열, 즉 작은 것 에서 큰 것 으로 정렬 된다.
    1. 헤더 파일 및 형식 정의
    #include<stdio.h>
    #include<stdlib.h>
    #define ElemType int	//        
    #define LEN 7			//      
    

    2. 함수 선언
    /*    */
    void Merge(ElemType A[], int low, int mid, int high);		//1.  
    void MergeSort(ElemType A[], int low, int high);			//2.     
    void Print(ElemType A[], int len);							//3.  
    

    3. 기본 조작
    3.1 병합
    //1.  
    ElemType* B = (ElemType*)malloc((LEN) * sizeof(ElemType));		//    B
    void Merge(ElemType A[], int low, int mid, int high) {
    	// A   A[low...mid] A[mid+1...high]    ,           
    	int i, j, k;
    	for (k = low; k <= high; k++)
    		B[k] = A[k];				// A        B 
    	for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
    		if (B[i] <= B[j])			//  B         
    			A[k] = B[i++];			//       A 
    		else
    			A[k] = B[j++];
    	}//for
    	while (i <= mid)
    		A[k++] = B[i++];	//         ,  
    	while (j <= high)
    		A[k++] = B[j++];	//         ,  
    }
    

    3.2 주요 과정
    //2.     
    void MergeSort(ElemType A[], int low, int high) {
    	if (low < high) {	
    		int mid = (low + high) / 2;		//          
    		MergeSort(A, low, mid);			//            
    		MergeSort(A, mid + 1, high);	//            
    		Merge(A, low, mid, high);		//  
    	}
    }
    

    3.3 출력
    //3.  
    void Print(ElemType A[], int len) {
    	for (int i = 0; i < len; i++)
    		printf("%d\t", A[i]);
    	printf("%
    "
    ); }

    4. main 함수
    int main() {
    
    	ElemType A[] = {49,38,65,97,76,13,27};
    	MergeSort(A, 0, LEN-1);	
    	Print(A, LEN);
    
    	return 0;
    }
    

    5. 소결
    1. 병합 의 개념
  • '병합' 의 의 미 는 두 개 또는 두 개 이상 의 질서 표를 새로운 질서 표 로 조합 하 는 것 이다.내부 정렬 에 서 는 보통 2 로 병합 된다.

  • 2. 병합 정렬 에 대한 성능 분석
  • 공간 복잡 도: O (n) 시간 복잡 도: O (nlog2n) 안정성: 안정 적 적용 성: 순서 저장 에 적용 되 는 선형 표
  • 3. 병합 정렬 의 관련 특징
  • m 길 을 병합 하고 하나의 요 소 를 선택 할 때마다 키워드 m - 1 회
  • 를 비교 해 야 합 니 다.
  • n 개 요 소 를 m 로 병합 하고 병합 횟수: * 8968 ° logmn * 8969 °
  • 좋은 웹페이지 즐겨찾기