# 1098. Insertion or Heap Sort (25) 21'

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> a, b;
//note:堆排序从1开始
int i = 1, j = i * 2;
while (j <= high) {
if(j + 1 <= high && b[j] < b[j] + 1)
j = j + 1;
if (b[i] < b[j]) {
swap(b[i], b[j]);
i = j;
j = i * 2;
}else break;
}
}

int main(){
int n;
cin >> n;
a.resize(n+1);
b.resize(n+1);
for (int i = 1; i <= n; i++)  cin >> a[i];
for (int i = 1; i <= n; i++)  cin >> b[i];
int i, j;
for (i = 1; i <= n - 1 && b[i] <= b[i+1]; i++);
for (j = i + 1; a[j] == b[j] && j <= n; j++) ;
if (j == n+1) {
cout << "Insertion Sort" << endl;
sort(b.begin() + 1, b.begin() + i + 2);
}else{
cout << "Heap Sort" << endl;
j = n;
while(j >= 2 && b[j] >= b[j - 1]) j--;
swap(b[1], b[j]);
}
for (int i = 1; i <= n; i++)
printf("%d%c", b[i], i == n ? '\n' : ' ');
return 0;
}

|
1月前
|

sort-04-heap sort 堆排序算法详解

13 0
|
1月前
|

sort-08-counting sort 计数排序

9 0
|
1月前
|

sort-07-merge sort 归并排序

8 0
|
1月前
|

25 2
|
8月前
|

185 1
|
11月前
|

91 0
|
11月前
|

|
C++
【PAT甲级 - C++题解】1098 Insertion or Heap Sort
【PAT甲级 - C++题解】1098 Insertion or Heap Sort
64 0
2-路插入排序(Two-Way Insertion Sort)

234 0
|

python实现【堆排序】(Heap Sort)
python实现【堆排序】(Heap Sort)
72 0