OpenJudge | 置换选择排序

总时间限定: 1000ms 内存限定: 65536kB
形貌
给定初始整数顺串，以及大小固定而且初始元素已知的二叉最小堆（为完全二叉树或类似完全二叉树，且父元素键值总小于等于任何一个子结点的键值），要求使用堆实现置换选择排序，并输出第一个顺串。比方给定初始顺串29,14,35,13,以及堆（记为16 19 31 25 21 56 40）， 置换选择排序得到的第一个顺串为16 19 21 25
。

输入

第一行包罗两个整数，m为初始顺串的数的个数，n为二叉最小堆的大小
第二行包罗m个整数，即初始顺串
第三行包罗n个整数，即已经建好的堆的元素（有序，按照从堆顶到堆底，从左到右的次序）
输出

输出包罗一行，即第一个顺串。
样例输入

1. 4 7
2. 29 14 35 13
3. 16 19 31 25 21 56 40

复制代码

样例输出

1. 16 19 21 25

复制代码

思路

• 我们知道这是一个小根堆，堆顶元素是最小的，我们可以将堆顶元素取出，将其放入res数组中，然后将堆顶元素删除，留意，在这一步当中是不消关注初始化顺串的元素的。
  
• 然后将初始的顺串中的下一个元素放入堆中，然后调整堆，使其满足堆的性质。
  
  
  • 假如初始的顺串被选中的元素比res数组中的最后一个元素大，那么就将这个元素放入堆中，然后调整堆；否则将这个元素先放入堆，然后与堆的最后一个元素交换，堆的大小减一，最后调整堆。
    
  
  
• 然后将堆顶元素取出，放入res数组中，然后将堆顶元素删除。
  
• 重复上述步骤2、3，直到堆为空大概初始顺串中的元素全部被更换。
  

看完原理，我们可以将代码分为两个部门，一个是调整堆的代码，一个是置换选择排序的代码。
代码剖析

先说调整堆的代码：

1. void reflushHeap(int n) {
2.     int i = 1;
3.         while(2*i <= n || 2*i+1 <= n) {
4.                 if(2*i <= n && 2*i+1 <= n) {
5.                         if(ar[2*i] < ar[2*i+1]) {
6.                                 if(ar[i] > ar[2*i]) {
7.                                         swap(ar[i], ar[2*i]);
8.                                         i = 2*i;
9.                                 }
10.                         } else {
11.                                 if(ar[i] > ar[2*i+1]) {
12.                                         swap(ar[i], ar[2*i+1]);
13.                                         i = 2*i+1;
14.                                 }
15.                         }
16.                 } else if(2*i <= n && 2*i+1 > n) {
17.                         if(ar[i] > ar[2*i]) {
18.                                 swap(ar[i], ar[2*i]);
19.                                 i = 2*i;
20.                         }       
21.                 } else break;
22.         }
23. }

复制代码

然后是置换选择排序的代码：
这代码在排除输入部门之后是如许的：

1. while(t--) {
2.     if(n <= 0) break;
3.     res.push_back(ar[1]);
4.     if(res.back() > in[j]) {
5.         ar[1] = in[j];
6.         swap(ar[1], ar[n]);
7.         --n;
8.         reflushHeap(n);
9.     } else {
10.         ar[1] = in[j];
11.         reflushHeap(n);
12.     }
13.     ++j;
14. }

复制代码

Code

1. #include <bits/stdc++.h>
2. #pragma GCC optimize(3,"Ofast","inline")
3. using namespace std;
5. int ar[1024], in[1024];
7. void reflushHeap(int n) {
8.         int i = 1;
9.         while(2*i <= n || 2*i+1 <= n) {
10.                 if(2*i <= n && 2*i+1 <= n) {
11.                         if(ar[2*i] < ar[2*i+1]) {
12.                                 if(ar[i] > ar[2*i]) {
13.                                         swap(ar[i], ar[2*i]);
14.                                         i = 2*i;
15.                                 }
16.                         } else {
17.                                 if(ar[i] > ar[2*i+1]) {
18.                                         swap(ar[i], ar[2*i+1]);
19.                                         i = 2*i+1;
20.                                 }
21.                         }
22.                 } else if(2*i <= n && 2*i+1 > n) {
23.                         if(ar[i] > ar[2*i]) {
24.                                 swap(ar[i], ar[2*i]);
25.                                 i = 2*i;
26.                         }       
27.                 } else break;
28.         }
29. }
31. int main() {
32.         vector<int> res;
33.         ios::sync_with_stdio(false);
34.         cin.tie(nullptr);
35.         cout.tie(nullptr);
36.         int m, n, t, j = 1;
37.         cin >> m >> n;
38.         res.reserve(m);
39.         for(int i = 1; i <= m; ++i) {
40.                 cin >> in[i];
41.         }
42.         for(int i = 1; i <= n; ++i) {
43.                 cin >> ar[i];
44.         }
45.         t = m;
46.         while(t--) {
47.                 if(n <= 0) break;
48.                 res.push_back(ar[1]);
49.                 if(res.back() > in[j]) {
50.                         ar[1] = in[j];
51.                         swap(ar[1], ar[n]);
52.                         --n;
53.                         reflushHeap(n);
54.                 } else {
55.                         ar[1] = in[j];
56.                         reflushHeap(n);
57.                 }
58.                 ++j;
59.         }
60.         for(auto i: res) {
61.                 cout << i << " ";
62.         }
63. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。