3. 堆排序

冷不防 2022-04-02 08:49 83阅读 0赞

实验要求：用堆排序算法按关键字递减的顺序排序。

程序输入：待排序记录数（整数）和待排序记录（整数序列）；

程序输出：建堆结果和建堆后第一、第二次筛选结果。（注：待排序记录数大于等于3）

<table> 
 <thead> 
  <tr> 
   <th>&nbsp;</th> 
   <th>测试输入<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=input&amp;lang=zh_cn" rel="nofollow"><img alt="关于“测试输入”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
   <th>期待的输出<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=expectedoutput&amp;lang=zh_cn" rel="nofollow"><img alt="关于“期待的输出”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
   <th>时间限制<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=timelimit&amp;lang=zh_cn" rel="nofollow"><img alt="关于“时间限制”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
   <th>内存限制<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=memlimit&amp;lang=zh_cn" rel="nofollow"><img alt="关于“内存限制”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
   <th>额外进程<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=nproc&amp;lang=zh_cn" rel="nofollow"><img alt="关于“{$a} 个额外进程”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>测试用例 1</td> 
   <td><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=77938&amp;test=100769&amp;type=in&amp;download=0" rel="nofollow">以文本方式显示</a> 
    <ol> 
     <li>6↵</li> 
     <li>11↵</li> 
     <li>12↵</li> 
     <li>16↵</li> 
     <li>14↵</li> 
     <li>15↵</li> 
     <li>10↵</li> 
    </ol></td> 
   <td><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=77938&amp;test=100769&amp;type=out&amp;download=0" rel="nofollow">以文本方式显示</a> 
    <ol> 
     <li>16&nbsp;15&nbsp;11&nbsp;14&nbsp;12&nbsp;10&nbsp;↵</li> 
     <li>15&nbsp;14&nbsp;11&nbsp;10&nbsp;12&nbsp;↵</li> 
     <li>14&nbsp;12&nbsp;11&nbsp;10&nbsp;↵</li> 
    </ol></td> 
   <td>1秒</td> 
   <td>64M</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>测试用例 2</td> 
   <td><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=77938&amp;test=100771&amp;type=in&amp;download=0" rel="nofollow">以文本方式显示</a> 
    <ol> 
     <li>9↵</li> 
     <li>9↵</li> 
     <li>8↵</li> 
     <li>7↵</li> 
     <li>6↵</li> 
     <li>5↵</li> 
     <li>4↵</li> 
     <li>3↵</li> 
     <li>2↵</li> 
     <li>1↵</li> 
    </ol></td> 
   <td><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=77938&amp;test=100771&amp;type=out&amp;download=0" rel="nofollow">以文本方式显示</a> 
    <ol> 
     <li>9&nbsp;8&nbsp;7&nbsp;6&nbsp;5&nbsp;4&nbsp;3&nbsp;2&nbsp;1&nbsp;↵</li> 
     <li>8&nbsp;6&nbsp;7&nbsp;2&nbsp;5&nbsp;4&nbsp;3&nbsp;1&nbsp;↵</li> 
     <li>7&nbsp;6&nbsp;4&nbsp;2&nbsp;5&nbsp;1&nbsp;3&nbsp;↵</li> 
    </ol></td> 
   <td>1秒</td> 
   <td>64M</td> 
   <td>0</td> 
  </tr> 
 </tbody> 
</table>

#include<stdio.h>  
    #include<stdlib.h>  
    
    int heap[200];  
    int length;
    void HeapAdjust(int x,int t)
    {    
        //i代表现在为止，j代表左右子树位置
        int i,j,up;
            i=x;
            j=2*i;
            up=heap[i];
            while(j<=t)
            {        if(j<t&&heap[j]<heap[j+1])
                            j++;
                    if(up<heap[j])
                    {        heap[i]=heap[j];
                            i=j;
                            j=2*i;
                    }
                    else
                    {        j=t+1;
                    }
            }
            heap[i]=up;
    }
    
    // void HeapAdjust( int x, int y)
    // {  
    //     int rc=heap[x];  
    //     for(int j=2*x;j<=y;j*=2){    
    //         if(j<y && rc < heap[j])
    //             j++;
    //         if(rc < heap[j])   
    //             break;        
    //         heap[x]=heap[j];  
    //         x=j;  
    //     }  
    //     heap[x]=rc;  
    //     heap[1]=heap[y];  
    // }  
    
    void HeapSort()   
    {  
        int i;    
        for(i = length/2; i>0; i--){  
            HeapAdjust(i,length);  
        }   
    
    }  
    
    int main() 
    {  
        scanf("%d",&length);  
        for(int i=1; i<=length ;i++)  
            scanf("%d",&heap[i]);  
        for(int q = 0; q < 3; q++){
            HeapSort();
            for(int i=1;i<=length;i++)  
                printf("%d ",heap[i]);  
            printf("\n");
            int temp = heap[1];
            heap[1] = heap[length];
            heap[length] = heap[1];
            length--;
        }
        return 1;
    }