【分析：】

n log₂ n的排序算法，不稳定，但时间复杂度不会被卡（快排有可能被卡成n²）

从小到大排序需要的是大根堆

当堆非空的时候，弹出堆顶元素，维护堆，在堆所用数组的最后存入弹出的堆顶元素

由于维护堆时堆的大小--，所以在堆所用数组的最后存入元素不会影响之后的操作

最后堆所用数组的元素便是从大到小排好的.

 

【代码：】

1 //堆排序 2 #include
     
       3 #include
      
        4 using namespace std; 5  6 const int MAXN = 100000 + 1; 7  8 int n, h_size; 9 int h[MAXN];10 11 inline void swap(int &x, int &y) {12     x ^= y, y ^= x, x ^= y;13 }14 15 void push(int x) {16     h[++h_size] = x;17     int now = h_size, next;18     while(now > 1) {19         next = now >> 1;20         if(h[now] > h[next])21             swap(h[now], h[next]);22         else break;23         now = next;24     }25 }26 int pop() {27     int ret = h[1];28     h[1] = h[h_size--];29     int now = 1, next;30     while((now << 1) <= h_size) {31         next = now << 1;32         if(next < h_size && h[next|1] > h[next]) ++next;33         if(h[now] < h[next])34             swap(h[now], h[next]);35         else break;36         now = next;37     }38     return ret;39 }40 41 void Que_sort() {42     while(h_size) {43         int num = pop();44         h[h_size + 1] = num;45     }46 }47 48 int main() {49     scanf("%d", &n);50     int num;51     for(int i = 1; i <= n; i++) {52         scanf("%d", &num);53         push(num);54     }55     Que_sort();56     for(int i = 1; i <= n; i++)57         printf("%d ", h[i]);58 }