数据结构OJ实验16-选择排序与堆排序与归并排序
A. DS排序--简单选择排序
题目描述
给出一个数据序列，使用简单选择排序算法进行升序排序。
输入
第一行输入t，表示有t个测试示例
第二行输入n，表示第一个示例有n个数据(n>1)
第三行输入n个数据，都是正整数，数据之间用空格隔开
以此类推
输出
对每组测试数据，输出每趟排序结果。不同组测试数据间用空行分隔。
样例查看模式?
正常显示查看格式
输入样例1?
2\n
5\n
12?58?36?47?96\n
10\n
1?3?6?9?0?8?5?7?4?2\n
输出样例1
12?58?36?47?96\n
12?36?58?47?96\n
12?36?47?58?96\n
12?36?47?58?96\n
\n
0?3?6?9?1?8?5?7?4?2\n
0?1?6?9?3?8?5?7?4?2\n
0?1?2?9?3?8?5?7?4?6\n
0?1?2?3?9?8?5?7?4?6\n
0?1?2?3?4?8?5?7?9?6\n
0?1?2?3?4?5?8?7?9?6\n
0?1?2?3?4?5?6?7?9?8\n
0?1?2?3?4?5?6?7?9?8\n
0?1?2?3?4?5?6?7?8?9\n
\n
AC代码
#include<iostream>
#include<vector>
using namespace std;
void display(vector<int>v)
{
int n = v.size();
for (int i = 0; i < n - 1; i++)
{
cout << v[i] << " ";
}
cout << v[n - 1] << endl;
}
void select(vector<int>&v)
{
int n=v.size();
for(int i=0;i<n-1;i++)
{
int temp=v[i];
int idxj=0;
bool flag=0;
for(int j=i+1;j<n;j++)
{
if(v[j]<temp)
{
temp=v[j];
idxj=j;
flag=1;
}
}
if(flag)swap(v[i],v[idxj]);
display(v);
}
}
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<int>a;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
a.push_back(x);
}
select(a);
cout << endl;
}
return 0;
}B. DS内排—堆排序
题目描述
给定一组数据，使用堆排序完成数据的降序排序。（建小顶堆)。
输入
数据个数n，n个整数数据
输出
初始创建的小顶堆序列
每趟交换、筛选后的数据序列，输出格式见样例
样例查看模式?
正常显示查看格式
输入样例1?
8?34?23?677?2?1?453?3?7\n
\n
输出样例1
8?1?2?3?7?23?453?677?34\n
8?2?7?3?34?23?453?677?1\n
8?3?7?453?34?23?677?2?1\n
8?7?23?453?34?677?3?2?1\n
8?23?34?453?677?7?3?2?1\n
8?34?677?453?23?7?3?2?1\n
8?453?677?34?23?7?3?2?1\n
8?677?453?34?23?7?3?2?1
AC代码
#include<iostream>
#include<vector>
using namespace std;
int n;
vector<int>a;
void min_heap(int st, int ed)
{
int p = st;
int son = st * 2 + 1;
while (son <= ed)
{
if (son + 1 <= ed && a[son] > a[son + 1])
{
son++;
}
if (a[p] < a[son])return;
swap(a[p], a[son]);
p = son;
son = 2 * p + 1;
}
}
void heap_sort()
{
for (int i = n / 2 - 1; i >= 0; i--)
{
min_heap(i, n - 1);
}
cout << n;
for (int i = 0; i < n; i++)
{
cout << " " << a[i];
}
cout << endl;
for (int i = n - 1; i > 0; i--)
{
swap(a[0], a[i]);
min_heap(0,i - 1);
cout << n;
for (int i = 0; i < n; i++)
{
cout << " " << a[i];
}
cout << endl;
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
a.push_back(x);
}
heap_sort();
return 0;
}C. DS内排—2-路归并排序
题目描述
输入一组字符串，用2-路归并排序按字典顺序进行降序排序。
输入
测试次数t
每组测试数据：数据个数n，后跟n个字符串，字符串不含空格。
输出
对每组测试数据，输出2-路归并排序的每一趟排序结果。每组测试数据的输出之间有1空行。
样例查看模式?
正常显示查看格式
输入样例1
2\n
6?shenzhen?beijing?guangzhou?futian?nanshan?baoan\n
10?apple?pear?peach?grape?cherry?dew?fig?haw?lemon?marc\n
\n
\n
输出样例1
shenzhen?beijing?guangzhou?futian?nanshan?baoan\n
shenzhen?guangzhou?futian?beijing?nanshan?baoan\n
shenzhen?nanshan?guangzhou?futian?beijing?baoan\n
\n
pear?apple?peach?grape?dew?cherry?haw?fig?marc?lemon\n
pear?peach?grape?apple?haw?fig?dew?cherry?marc?lemon\n
pear?peach?haw?grape?fig?dew?cherry?apple?marc?lemon\n
pear?peach?marc?lemon?haw?grape?fig?dew?cherry?apple
AC代码
#include<iostream>
#include<vector>
using namespace std;
void print(vector<string>k)
{
for (int i = 1; i < k.size() - 1; i++)
{
cout << k[i] << " ";
}
cout << k[k.size() - 1] << endl;
}
void merge(vector<string>& k, vector<string>& d,int l,int m,int r)
{
int i = l, j = m + 1, kk = l;
while (i <= m && j <= r)
{
if (k[i] >= k[j])d[kk++] = k[i++];
//降序
else d[kk++] = k[j++];
}
while (i <= m)d[kk++] = k[i++];
while (j <= r)d[kk++] = k[j++];
}
void merge_sort(vector<string>& k, vector<string>& d)
{
int len = k.size() - 1;
int l, m, r, i;
for (i = 1; i < len; i *= 2)//区间长度
{
for (l = 1; l <= len; l += 2 * i)//区间起始点
{
m = l + i - 1;
if (m >= len)break;
r = l + 2 * i - 1;
if (r > len)r = len;
merge(k, d, l, m, r);
}
for (int t = 1; t <= len; t++)k[t] = d[t];
print(k);
}
}
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<string>key(n + 1);
vector<string>data(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> key[i];
}
merge_sort(key, data);
cout << endl;
}
return 0;
}D. 奥运排行榜
题目描述
每年奥运会各大媒体都会公布一个排行榜，但是细心的读者发现，不同国家的排行榜略有不同。比如中国金牌总数列第一的时候，中国媒体就公布“金牌榜”；而美国的奖牌总数第一，于是美国媒体就公布“奖牌榜”。如果人口少的国家公布一个“国民人均奖牌榜”，说不定非洲的国家会成为榜魁…… 现在就请你写一个程序，对每个前来咨询的国家按照对其最有利的方式计算它的排名。
输入
输入的第一行给出两个正整数N和M（≤224，因为世界上共有224个国家和地区），分别是参与排名的国家和地区的总个数、以及前来咨询的国家的个数。为简单起见，我们把国家从0 ~?N?1编号。之后有N行输入，第i行给出编号为i?1的国家的金牌数、奖牌数、国民人口数（单位为百万），数字均为[0,1000]区间内的整数，用空格分隔。最后面一行给出M个前来咨询的国家的编号，用空格分隔。
输出
在一行里顺序输出前来咨询的国家的排名:计算方式编号。其排名按照对该国家最有利的方式计算；计算方式编号为：金牌榜=1，奖牌榜=2，国民人均金牌榜=3，国民人均奖牌榜=4。输出间以空格分隔，输出结尾不能有多余空格。
若某国在不同排名方式下有相同名次，则输出编号最小的计算方式。
样例查看模式?
正常显示查看格式
输入样例1?
4?4\n
51?100?1000\n
36?110?300\n
6?14?32\n
5?18?40\n
0?1?2?3
输出样例1
1:1?1:2?1:3?1:4
AC代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct country
{
int num;
int gold;
int medal;
int people;
};
int n, m;
vector<country>c;
vector<pair<int, int>>gg;
vector<pair<int, int>>mm;
vector<pair<double, int>>agg;
vector<pair<double, int>>amm;
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
int x, y, z;
cin >> x >> y >> z;
c.push_back({ i,x,y,z });
gg.push_back({ x,i });
mm.push_back({ y,i });
agg.push_back({ (1.0 * x) / z,i });
amm.push_back({ (1.0 * y) / z,i });
}
sort(gg.rbegin(), gg.rend());
sort(mm.rbegin(), mm.rend());
sort(agg.rbegin(), agg.rend());
sort(amm.rbegin(), amm.rend());
for (int i = 0; i < m; i++)
{
int x;
cin >> x;
int paiming = n;
int idx = 0;
for (int j = 0; j < n; j++)
{
if (amm[j].second == x)
{
if (paiming >= j + 1)
{
paiming = j + 1;
idx = 4;
break;
}
}
}
for (int j = 0; j < n; j++)
{
if (agg[j].second == x)
{
if (paiming >= j + 1)
{
paiming = j + 1;
idx = 3;
break;
}
}
}
for (int j = 0; j < n; j++)
{
if (mm[j].second == x)
{
if (paiming >= j + 1)
{
paiming = j + 1;
idx = 2;
break;
}
}
}
for (int j = 0; j <n; j++)
{
if (gg[j].second == x)
{
if (paiming >= j+1)
{
paiming = j+1;
idx = 1;
break;
}
}
}
cout << paiming << ":" << idx;
if (i != m - 1)cout << " ";
else cout << endl;
}
return 0;
}E. 关于堆的判断
题目描述
将一系列给定数字顺序插入一个初始为空的小顶堆H[]。随后判断一系列相关命题是否为真。命题分下列几种：
x is the root：x是根结点；x and y are siblings：x和y是兄弟结点；x is the parent of y：x是y的父结点；x is a child of y：x是y的一个子结点。
输入
每组测试第1行包含2个正整数N（≤?1000）和M（≤?20），分别是插入元素的个数、以及需要判断的命题数。下一行给出区间[?10000,10000]内的N个要被插入一个初始为空的小顶堆的整数。之后M行，每行给出一个命题。题目保证命题中的结点键值都是存在的。
输出
对输入的每个命题，如果其为真，则在一行中输出T，否则输出F。
样例查看模式?
正常显示查看格式
输入样例1?
5?4\n
46?23?26?24?10\n
24?is?the?root\n
26?and?23?are?siblings\n
46?is?the?parent?of?23\n
23?is?a?child?of?10
输出样例1
F\n
T\n
F\n
T
AC代码
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<string>
using namespace std;
const int N = 1e5 + 10;
int n, m;
map<int, int>mp;
int h[N];
int cnt;
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
swap(h[u], h[u / 2]);
u /= 2;
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
h[++cnt] = x;
up(i);
}
getchar();
for (int i = 1; i <= n; i++)mp[h[i]] = i;
for (int i = 0; i < m; i++)
{
string s;
getline(cin, s);
vector<string>tt;
string temp;
for (int i = 0; i < s.size(); i++)
{
if (s[i] != ' ')temp += s[i];
else
{
tt.push_back(temp);
temp.clear();
}
}
tt.push_back(temp);
int nn = tt.size();
int num1 = stoi(tt[0]);
int num2 = 0;
if (tt[nn - 1] == "root")
{
if (mp[num1] == 1)
{
cout << "T" << endl;
}
else cout << "F" << endl;
continue;
}
if (tt[nn - 1] == "siblings")
{
num2 = stoi(tt[2]);
if (mp[num1]/2 ==mp[num2]/2)
{
cout << "T" << endl;
}
else cout << "F" << endl;
continue;
}
if (tt[3] == "parent")
{
num2 = stoi(tt[nn - 1]);
if (mp[num1] == mp[num2]/2)
{
cout << "T" << endl;
}
else cout << "F" << endl;
continue;
}
if (tt[3] == "child")
{
num2 = stoi(tt[nn - 1]);
if (mp[num1]/2 == mp[num2])
{
cout << "T" << endl;
}
else cout << "F" << endl;
continue;
}
}
return 0;
}F. 插入排序还是归并排序
题目描述
根据维基百科的定义：
插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。
现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？
输入
输入在第一行给出正整数 N (≤100)；随后一行给出原始序列的 N 个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。
输出
首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。
样例查看模式?
正常显示查看格式
输入样例1?
10\n
3?1?2?8?7?5?9?4?6?0\n
1?2?3?7?8?5?9?4?6?0
输出样例1
Insertion?Sort\n
1?2?3?5?7?8?9?4?6?0
AC代码
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<string>
using namespace std;
vector<int>check;
vector<vector<int>>mm;
vector<vector<int>>ii;
void print(vector<int>k)
{
for (int i = 1; i < k.size() - 1; i++)
{
cout << k[i] << " ";
}
cout << k[k.size() - 1] << endl;
}
void merge(vector<int>& k, vector<int>& d, int l, int m, int r)
{
int i = l, j = m + 1, kk = l;
while (i <= m && j <= r)
{
if (k[i] <= k[j])d[kk++] = k[i++];
else d[kk++] = k[j++];
}
while (i <= m)d[kk++] = k[i++];
while (j <= r)d[kk++] = k[j++];
}
void merge_sort(vector<int>& k, vector<int>& d)
{
int len = k.size() - 1;
int l, m, r, i;
for (i = 1; i < len; i *= 2)//区间长度
{
vector<int>kk;
for (l = 1; l <= len; l += 2 * i)//区间起始点
{
m = l + i - 1;
if (m >= len)break;
r = l + 2 * i - 1;
if (r > len)r = len;
merge(k, d, l, m, r);
}
for (int t = 1; t <= len; t++)k[t] = d[t];
for (int t = 1; t <= len; t++)
{
kk.push_back(k[t]);
}
mm.push_back(kk);
}
}
void insert_sort(vector<int>& a)
{
int n = a.size()-1;
for (int i = 2; i < n; i++)
{
int j;
int tt = a[i];
vector<int>kk;
for (j = i - 1; j >= 1; j--)
{
if (a[j] > tt)
{
a[j + 1] = a[j];
}
else break;
}
a[j + 1] = tt;
for (int i = 1; i <= n; i++)
{
kk.push_back(a[i]);
}
ii.push_back(kk);
}
}
int main()
{
int nn;
cin >> nn;
vector<int>k1(nn + 1);
vector<int>mk1(nn + 1);
vector<int>k2(nn+1);
for (int i = 1; i <= nn; i++)
{
cin >> k1[i];
k2[i] = k1[i];
}
for (int i = 0; i <nn; i++)
{
int x;
cin>>x;
check.push_back(x);
}
insert_sort(k2);
merge_sort(k1, mk1);
bool ok = 0;
for (int i = 0; i < mm.size(); i++)
{
if (check == mm[i])
{
ok = 1;
cout << "Merge Sort" << endl;
for (int j = 0; j < mm[i + 1].size(); j++)
{
if (j == 0)cout << mm[i + 1][j];
else cout <<" "<< mm[i + 1][j];
}
break;
}
}
if (!ok)
{
for (int i = 0; i < ii.size(); i++)
{
if (check == ii[i])
{
cout << "Insertion Sort" << endl;
for (int j = 0; j < ii[i + 1].size(); j++)
{
if (j == 0)cout << ii[i + 1][j];
else cout << " " << ii[i + 1][j];
}
break;
}
}
}
return 0;
}本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！