n个数求前m个数的大小

布满荆棘的人生 2023-12-31 07:20 19阅读 0赞

一、描述

n个数求前m个数的大小

二、分析

堆排序就是先求出最大的数，然后求出次大的数，然后求出第三大的数，依次类推，而这个题只要求求出前m个大的数，所以用堆排序应该是效率比较高的。

三、代码

void heapfy(int a[],int i,int heapsize)
    {
         int largest=i;
         int left=2*i+1;
         int right=left+1;
         if(left<heapsize && a[i]<a[left])  
               largest=left;
         if(right<heapsize && a[largest]<a[right])
               largest=right;
         if(largest!=i)
         {
               swap(a[i],a[largest]);
               heapfy(a,largest);
         }
    }
    void buildheap(int a[],int n)
    {
          
          for(int i=len/2-1;i>=0;i--)
              heapfy(a,i,len);
    }
    void heapsort(int n，int m)  //题解代码
    {  
        int i;  
        int a[10]={9,3,4,5,1,8,0,2,7,6};
        int n=10;//a的长度
        int heapsize=m;  
        build_max_heap(a,heapsize);  
        printf("%d",a[1]);  
        m--;  
        for (i=n;i>=1;i--)  
        {      
            if (m==0)  
                break;  
            printf(" ");  
            swap(a[1],a[i]);  
            heapsize--;   
            heapfy(a,i,heapsize);    
            printf("%d",a[1]);  
            m--;  
        }  
    }  
    
    
    
    
    void sortheap(int a[],int len)//堆排序代码
    {
       
        for(int i=n-1;i>=0;i--)
        {
             swap(a[0],a[i]);
             heapfy(a,0,i);
        }
    }