堆排序

 1 #include<iostream>
 2 using namespace std;
 3 
 4 
 5 void Max_Heapify(int a[],int heap_size, int i)//修复堆
 6 {
 7     int largest;
 8     int l = 2 * i;
 9     int r = 2 * i + 1;
10     if (l <= heap_size&&a[l] > a[i])
11         largest = l;
12     else largest = i;
13     if (r <= heap_size&&a[r] > a[largest])
14         largest = r;
15     if (largest != i)
16     {
17         int t = a[i];
18         a[i] = a[largest];
19         a[largest] = t;
20         Max_Heapify(a, heap_size, largest);
21     }
22 }
23 
24 
25 void Build_Max_Heap(int a[], int size, int i)//产生最大堆
26 {
27     int l = 2 * i;
28     int r = 2 * i + 1;
29     if (l <= size)
30         Build_Max_Heap(a, size, l);
31     if (r <= size)
32         Build_Max_Heap(a, size, r);
33     Max_Heapify(a, size, i);
34 }
35 
36 
37 void Heapsort(int a[], int size)//最终算法实现
38 {
39     Build_Max_Heap(a, size, 1);
40     int Heap_size = size;
41     while (Heap_size > 1)
42     {
43         int t = a[1];
44         a[1] = a[Heap_size];
45         a[Heap_size] = t;
46         Heap_size--;
47         Max_Heapify(a, Heap_size, 1);
48     }
49 }
50 
51 
52 void main()
53 {
54     int a[11];
55     for (int i = 1; i < 11; i++)
56         a[i] = 11 - i;
57     Heapsort(a, 10);
58     for (int i = 1; i < 11; i++)
59         cout << a[i] << endl;
60 
61 }