堆排序

 1 // 堆排序.cpp : 定义控制台应用程序的入口点。
 2 
 3 #include "stdafx.h"
 4 #include <string.h>
 5 #define MAX 100
 6 
 7 void swap(int &a,int &b)
 8 {
 9     int c;
10     c=a;
11     a=b;
12     b=c;
13 }
14 
15 void max_heapity(int heap[],int i,int len)//保持最大堆性质
16 {
17     int left=2*i, right=2*i+1,largest=-1;
18     if((left<=len)&&(heap[left]>heap[i]))
19         largest=left;
20     else 
21         largest=i;
22     if((right<=len)&&(heap[right]>heap[largest]))
23         largest=right;
24     if(largest!=i)
25         {
26             swap(heap[largest],heap[i]);
27             max_heapity(heap,largest,len);
28         }
29 }
30 
31 void build_maxheap(int heap[],int len) //建立最大堆
32 {
33     int index=len/2;
34     for(int i=index;i>=1;i--)
35          max_heapity(heap,i,len);
36 }
37 
38 void heap_sort(int heap[],int len)//堆排序
39 {
40     build_maxheap(heap,len);
41     for(int i=len;i>=2;i--)
42     {
43         swap(heap[1],heap[i]);//每次将最大值放在最后一个结点中
44         len-=1;
45         max_heapity(heap,1,len);
46     }
47 }
48 
49 void main()
50 {
51     int a[MAX],lengh;
52     printf("input a number:\n");
53     scanf("%d",&lengh);
54     printf("input %d number:\n",lengh);
55     for(int j=1;j<=lengh;j++) //注意i值要从1开始
56     {
57         scanf("%d",&a[j]);
58     }
59     heap_sort(a,lengh);
60     for(int i=1;i<=lengh;i++) //最终结果按从小到大排序输出
61         printf("%4d",a[i]);
62     printf("\n");
63 }