pta 6-11 求自定类型元素序列的中位数

川长思鸟来 2022-06-01 07:41 94阅读 0赞

\#\#\#问题描述  
本题要求实现一个函数，求N个集合元素A\[\]的中位数，即序列中第⌊(N+1)/2⌋大的元素。其中集合元素的类型为自定义的ElementType。

其中给定集合元素存放在数组A\[\]中，正整数N是数组元素个数。该函数须返回N个A\[\]元素的中位数，其值也必须是ElementType类型。

--------------------

\#\#\#分析  
//先排序，再找第中间大的数。  
//还有就是找到数组中第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<N-d;j+=d){
    				for(k=j;k<N;k+=d){
    		            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)<N; i = child){
    	   child = 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];
    }