pta 6 - 11 자체 유형 요소 시퀀스 의 중위 수 구하 기

문제 설명
이 문 제 는 하나의 함 수 를 실현 하고 N 개의 집합 요소 A [] 의 중위 수 를 구 해 야 한다. 즉, 서열 에서 전체 8970 ° N / 2 + 1 * 8971 ° 큰 요 소 를 구 해 야 한다.그 중에서 집합 요소 의 유형 은 사용자 정의 Element Type 입 니 다.
그 중에서 주어진 집합 요 소 는 배열 A [] 에 저장 되 고 정수 N 은 배열 요소 의 개수 입 니 다.이 함 수 는 N 개의 A [] 요소 의 중위 수 를 되 돌려 야 하 며, 그 값 도 Element Type 형식 이 어야 합 니 다.
분석 하 다.
/ / 먼저 정렬 하고 중간 에 큰 수 를 찾 습 니 다. /그리고 배열 에서 k 번 째 로 큰 수 를 찾 는 것 입 니 다. 하 나 는 빠 른 선택 알고리즘 이 라 고 하 는데 빠 른 정렬 에 따라 수정 합 니 다.다른 하 나 는 우선 대기 열, 우선 대기 열 과 정렬 사상 이 유사 하 다.
1. 거품

  ElementType Median( ElementType A[], int N ){
    //   ，        
    int i , j;
    ElementType temp;
    for(i=0; i < N - 1; i++){
        for(j=0;j < N-i -1; j++){
           if(A[j]>A[j+1]){
               temp = A[j];
               A[j] = A[j+1];
               A[j+1] = temp;
           }
        }
    }
    return A[N/2];
}  

2. 해시

    ElementType Median( ElementType A[], int N ){
    //                  
    int d, i , j, k;
    ElementType temp;
    for(d = N/2; d >= 1; d/=2){
        for(i=0;i < d; i++){
            for(j=i;j
                for(k=j;k
                    if(A[j]>A[k]){
                        temp = A[j];
                         A[j] = A[k];
                        A[k] = temp;
                    }  
                } 
            }
        }
    }
    return A[N/2];
}

ElementType Median( ElementType A[], int N ){
    //   ，    
    int d, i , j, k;
    ElementType temp;
    for(d = N/2; d >= 1; d/=2){
        for(i=d;i < N; i++){
            for(j=i-d;j>=0&&A[j]>A[j+d];j-=d){
                   temp = A[j];
                   A[j] = A[j+d];
                   A[j+d] = temp;  
            }
        }
    }
    return A[N/2];
}

void shellSort(ElementType A[], int N){
  int i, j, h;
  ElementType tem;
  for(h = N/2; h > 0; h /= 2){
    for(i = h; i < N; i++){
       tem = A[i]; 
       for(j = i; j >= h; j -= h)  //           
          if(tem < A[j-h]) A[j] = A[j-h];    
          else break;
       A[j] = tem;
    }
  }
}
ElementType Median( ElementType A[], int N ){
    shellSort(A,N);
    return A[N/2];
}

3. 쌓 기 정렬

/**
*          。
*      ，     i > N/2-1。         
*/
#define LeftChild(i)(2*(i)+1) 
//    2*i+1?   2*i？
//       0   。   1      2*i。

void preDown(ElementType A[],int i, int N){
    int child;
    ElementType tem;
    for(tem = A[i]; LeftChild(i)//       
       if(child != N-1 && A[child + 1]>A[child]) child++;  //       ，     ，      
       if(tem < A[child])  A[i] = A[child];  //          ，      。
       else break;  //        ，   。
    }
    A[i] = tem; //       ， i   ;       ， i  child。
}

void swap(ElementType *a, ElementType *b){
    ElementType temp;  
    temp = *a;  
    *a = *b;  
    *b = temp;
}

void heapSort(ElementType A[], int N){
   int i;
   for(i = N/2; i >= 0; i --) preDown(A,i,N);  //    
   for(i = N-1; i > 0; i --){       //####   
      swap(&A[0],&A[i]);  //               
      preDown(A,0,i);   //           
   }
   //      ，     。
}

ElementType Median( ElementType A[], int N ){
    //   
    heapSort(A,N);
    return A[N/2];
}