判断是否是插入排序的部分与 1035 插入与归并一样。

本题主要考察 堆排序的实现。

首先，把所有双亲结点进行向下调整；

然后，重复 n-1 次操作，即 把堆顶元素与待排序区的最后一个元素交换并对堆顶元素向下调整。

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 const int maxn = 200;
 6 int n;
 7 int origin[maxn],temp[maxn];
 8 
 9 //向下调整
10 void downAjust(int low,int high) { //low为待调整的双亲结点，high是最后一个叶子结点
11     int i = low,j = i*2;
12     while( j <= high) {
13         //右孩子存在，且大于左孩子
14         if(j + 1 <= high && origin[j+1] > origin[j])
15             j = j +1;
16         //根结点小于孩子结点
17         if(origin[i] < origin[j]) {
18             swap(origin[i],origin[j]);
19             i = j;
20             j = i*2;
21         } else break;
22     }
23 }
24 
25 //建立大顶堆
26 void create() {
27     //从倒数第一个双亲结点 到 根结点进行 向下调整
28     for(int i = n/2; i>=1; --i)
29         downAjust(i,n);
30 }
31 
32 int main() {
33     cin>>n;
34     for(int i = 1; i <= n; ++i)
35         cin>>origin[i];
36     for(int i = 1; i <= n; ++i)
37         cin>>temp[i];
38     int i,j;
39     for(i = 1; i+1 <= n && temp[i] <= temp[i+1]; ++i);
40     for(j = i+1; j <= n && temp[j] == origin[j]; ++j);
41     if(j > n) {
42         printf("Insertion Sort\n");
43         sort(temp+1,temp+i+2);
44         for(i = 1 ; i <= n; ++i) {
45             if(i > 1) printf(" ");
46             printf("%d",temp[i]);
47         }
48     } else {
49         printf("Heap Sort\n");
50         create(); //建立大顶堆
51         for(i = n; i > 1; --i) { //堆排序
52             swap(origin[1],origin[i]);//堆顶元素覆盖最后一个元素
53             downAjust(1,i-1);
54             for(j = 1; j <= n && origin[j] == temp[j]; ++j);//中间序列比较
55             if( j > n) break;
56         }
57         --i;
58         swap(origin[1],origin[i]);
59         downAjust(1,i-1);
60         for(i = 1 ; i <= n; ++i) {
61             if(i > 1) printf(" ");
62             printf("%d",origin[i]);
63         }
64     }
65     return 0;
66 }