堆排序

梦里伊人 posted @ 2007年8月07日 23:15 in c语言笔记 , 1331 阅读
  1. #include<stdio.h>
  2.  
  3. int k,j;
  4. /* 建堆函数 */
  5. void build(int *a,int i,int n)
  6. {
  7.     int tmp;
  8.     k=i;
  9.     j=2*k+1;
  10.     while(j<=n)
  11.         {
  12.         if(j<n&&a[j]<a[j+1])
  13.             j++;
  14.         if(a[k]>=a[j])
  15.                         break;
  16.         tmp=a[k];
  17.         a[k]=a[j];
  18.         a[j]=tmp;       
  19.         k=j;
  20.         j=2*j+1;
  21.     }
  22. }
  23. /* 打印数组函数 */
  24. void print(int *a,int n)
  25. {
  26.     int i;
  27.     printf("\n");
  28.     for(i=0;i<n;i++)
  29.             printf("%d\t",a[i]);
  30.     printf("\n");
  31. }
  32. /* 打印堆函数 */
  33. void printhp(int *a,int b1,int b2)
  34. {
  35.     int size;
  36.     int h=0,sum=0,item=1;
  37.     int i,j,cnt,start,tmp;
  38.     size=b2-b1+1;
  39.     while(sum<=size)
  40.         {
  41.         sum+=item;
  42.         h++;
  43.         item*=2;
  44.     }
  45.     item=1;
  46.     cnt=0;
  47.     start=b1;
  48.     tmp=1;
  49.     printf("\n--------------------------------------------\n");   
  50.     printf("  堆：\n");
  51.     while(1)
  52.     {
  53.             for(i=0;i<h;i++)
  54.             {
  55.                  for(j=0;j<h-i;j++)
  56.                        printf("    ");
  57.                  for(j=0;j<i+1;j++)
  58.                        printf(" ");
  59.                  for(j=0;j<tmp;j++)
  60.                  {
  61.                        if(cnt>size-1)
  62.                               goto end;
  63.                        printf("%4d",a[cnt++]);
  64.                  }
  65.                 printf("\n");
  66.                 tmp*=2;
  67.             }     
  68.      }
  69.      end:
  70.           printf("\n");       
  71.           return;                 
  72. }
  73. /* 打印已排序数组函数 */
  74. void printar(int *a,int b2,int len)
  75. {
  76.    int i;
  77.    printf("  已排序：\n");
  78.    for(i=0;i<b2;i++)
  79.        printf("   ");       
  80.    for(i=b2;i<=len;i++)
  81.            printf("%d\t",a[i]);       
  82.    printf("\n");
  83. }
  84.  
  85. main()
  86. {
  87.     int a[50];
  88.     int i,tmp,len;
  89.     printf("                   堆排序\n");
  90.     printf("\n============================================\n");   
  91.     printf("\n  请输入待排序数组中元素的个数,以回车结束：\n");
  92.     scanf("%d",&len);   
  93.     printf("\n  请输入待排序数组,以回车结束：\n");
  94.     for(i=0;i<len;i++)
  95.         scanf("%d",&a[i]);       
  96.     printf("\n============================================\n");   
  97.     printf("\n  初始数组：            \n");   
  98.     print(a,len);   
  99.     /* 建初始堆 */
  100.     for(i=(len-1)/2;i>=0;i--)
  101.         build(a,i,len-1);     
  102.     printhp(a,0,len-1);     
  103.     /* 改建堆 */
  104.     for(i=0;i<len-1;i++)
  105.     {
  106.         tmp=a[0];
  107.         a[0]=a[len-1-i];
  108.         a[len-1-i]=tmp;
  109.         build(a,0,len-2-i);
  110.         printhp(a,0,len-2-i);
  111.         printar(a,len-1-i,len-1);       
  112.     }
  113.     printf("\n--------------------------------------------\n");
  114.     printf("\n  排序结果：\n");       
  115.     print(a,len);
  116.     printf("\n============================================\n\n");   
  117.   }
  118.  
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter



Host by is-Programmer.com | Power by Chito 1.3.3 beta | Designed by Wink Hosting.