数据结构OJ实验16-选择排序与堆排序与归并排序

2024-01-07 20:15:42

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 rootx是根结点;
  • x and y are siblingsxy是兄弟结点;
  • x is the parent of yxy的父结点;
  • x is a child of yxy的一个子结点。

输入

每组测试第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;
}

文章来源:https://blog.csdn.net/gyeolhada/article/details/135347443
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。