堆排序

 1 #include<iostream>
 2 #include<vector>
 3 #include <bitset>
 4 #include<algorithm>
 5 #include<map>
 6 #include<unordered_map>
 7 #include<string>
 8 #include<unordered_set>
 9 #include<set>
10 using namespace std;
11 
12 void Heapfy(int a[], int idx, int max)//堆调整
13 {
14     int left = idx * 2 + 1;
15     int right = left + 1;
16     int largest = idx;
17     if (left<max&&a[left]>a[largest])// 大于号是升序，小于号是降序
18     {
19         largest = left;
20     }
21     if (right < max&&a[right]>a[largest])// 大于号是升序，小于号是降序
22     {
23         largest = right;
24     }
25     if (largest != idx)
26     {
27         int temp = a[largest];
28         a[largest] = a[idx];
29         a[idx] = temp;
30         Heapfy(a, largest, max);
31     }
32 }
33 void buildHeap(int a[], int ll)
34 {
35     int len = ll;
36     for (int i = len / 2 - 1; i >= 0; --i) //第一次，将数据调整为堆
37     {
38         Heapfy(a, i, len);
39     }
40     for (int i = len - 1; i >= 1; --i)   // 利用堆进行排序
41     {
42         int temp = a[0];
43         a[0] = a[i];
44         a[i] = temp;
45         Heapfy(a, 0, i);
46     }
47 }
48 int main()
49 {
50     int a[] = { 1, 5, 8, 6, 6, 48, 23, 0, 4, 0 };
51     int n = sizeof(a) / sizeof(a[0]);
52     cout << n << endl;
53     for (int i = 0; i < n; i++)
54     {
55         cout << a[i] << " ";
56     }
57     cout << endl;
58     buildHeap(a, n);
59     for (int i = 0; i < n; i++)
60     {
61         cout << a[i] << " ";
62     }
63     cout << endl;
64 
65     system("pause");
66     return 0;
67 }