OpenJudge | 置换选择排序
总时间限定: 1000ms 内存限定: 65536kB形貌
给定初始整数顺串，以及大小固定而且初始元素已知的二叉最小堆（为完全二叉树或类似完全二叉树，且父元素键值总小于等于任何一个子结点的键值），要求使用堆实现置换选择排序，并输出第一个顺串。比方给定初始顺串29,14,35,13,以及堆（记为16 19 31 25 21 56 40）， 置换选择排序得到的第一个顺串为16 19 21 25
。
https://i-blog.csdnimg.cn/direct/34f0390f5f384d8797d8ef43adf47c39.png
输入
第一行包罗两个整数，m为初始顺串的数的个数，n为二叉最小堆的大小
第二行包罗m个整数，即初始顺串
第三行包罗n个整数，即已经建好的堆的元素（有序，按照从堆顶到堆底，从左到右的次序）
输出
输出包罗一行，即第一个顺串。
样例输入
4 7
29 14 35 13
16 19 31 25 21 56 40
样例输出
16 19 21 25
思路
[*]我们知道这是一个小根堆，堆顶元素是最小的，我们可以将堆顶元素取出，将其放入res数组中，然后将堆顶元素删除，留意，在这一步当中是不消关注初始化顺串的元素的。
[*]然后将初始的顺串中的下一个元素放入堆中，然后调整堆，使其满足堆的性质。
[*]假如初始的顺串被选中的元素比res数组中的最后一个元素大，那么就将这个元素放入堆中，然后调整堆；否则将这个元素先放入堆，然后与堆的最后一个元素交换，堆的大小减一，最后调整堆。
[*]然后将堆顶元素取出，放入res数组中，然后将堆顶元素删除。
[*]重复上述步骤2、3，直到堆为空大概初始顺串中的元素全部被更换。
看完原理，我们可以将代码分为两个部门，一个是调整堆的代码，一个是置换选择排序的代码。
代码剖析
先说调整堆的代码：
void reflushHeap(int n) {
int i = 1;
while(2*i <= n || 2*i+1 <= n) {
if(2*i <= n && 2*i+1 <= n) {
if(ar < ar) {
if(ar > ar) {
swap(ar, ar);
i = 2*i;
}
} else {
if(ar > ar) {
swap(ar, ar);
i = 2*i+1;
}
}
} else if(2*i <= n && 2*i+1 > n) {
if(ar > ar) {
swap(ar, ar);
i = 2*i;
}
} else break;
}
}
然后是置换选择排序的代码：
这代码在排除输入部门之后是如许的：
while(t--) {
if(n <= 0) break;
res.push_back(ar);
if(res.back() > in) {
ar = in;
swap(ar, ar);
--n;
reflushHeap(n);
} else {
ar = in;
reflushHeap(n);
}
++j;
}
Code
#include <bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
int ar, in;
void reflushHeap(int n) {
int i = 1;
while(2*i <= n || 2*i+1 <= n) {
if(2*i <= n && 2*i+1 <= n) {
if(ar < ar) {
if(ar > ar) {
swap(ar, ar);
i = 2*i;
}
} else {
if(ar > ar) {
swap(ar, ar);
i = 2*i+1;
}
}
} else if(2*i <= n && 2*i+1 > n) {
if(ar > ar) {
swap(ar, ar);
i = 2*i;
}
} else break;
}
}
int main() {
vector<int> res;
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int m, n, t, j = 1;
cin >> m >> n;
res.reserve(m);
for(int i = 1; i <= m; ++i) {
cin >> in;
}
for(int i = 1; i <= n; ++i) {
cin >> ar;
}
t = m;
while(t--) {
if(n <= 0) break;
res.push_back(ar);
if(res.back() > in) {
ar = in;
swap(ar, ar);
--n;
reflushHeap(n);
} else {
ar = in;
reflushHeap(n);
}
++j;
}
for(auto i: res) {
cout << i << " ";
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]