数据结构OJ实验15-插入排序与交换排序

A. DS内排—直插排序

题目描述

给定一组数据，使用直插排序完成数据的升序排序。

--程序要求--

若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio

程序中若include多过一个头文件，不看代码，作0分处理

不允许使用第三方对象或函数实现本题的要求

输入

数据个数n，n个数据

输出

直插排序的每一趟排序结果

样例查看模式?

正常显示查看格式

输入样例1?

7?34?23?677?2?1?453?3

输出样例1

23?34?677?2?1?453?3\n
23?34?677?2?1?453?3\n
2?23?34?677?1?453?3\n
1?2?23?34?677?453?3\n
1?2?23?34?453?677?3\n
1?2?3?23?34?453?677\n

AC代码

#include<iostream>
using namespace std;
const int N = 1e5;
int a[N];
int n;
void insert_sort()
{
    for (int i = 1; i < n; i++)
    {
        int t = a[i];
        int j;
        for (j = i - 1; j >= 0; j--)
        {
            if (a[j] > t)
            {
                a[j + 1] = a[j];
            }
            else break;
        }
        a[j+1] = t;
        for (j = 0; j < n; j++)
        {
            cout << a[j];
            if (j != n - 1)cout << " ";
            else cout << endl;
        }

    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    insert_sort();
    return 0;
}

B. DS排序--希尔排序

题目描述

给出一个数据序列，使用希尔排序算法进行降序排序。

间隔gap使用序列长度循环除2直到1

输入

第一行输入t，表示有t个测试示例
第二行输入n，表示第一个示例有n个数据(n>1)
第三行输入n个数据，都是正整数，数据之间用空格隔开
以此类推

输出

对每组测试数据，输出每趟排序结果。不同组测试数据间用空行分隔。

样例查看模式?

正常显示查看格式

输入样例1?

2\n
6\n
111?22?6?444?333?55\n
8\n
77?555?33?1?444?77?666?2222\n

输出样例1

444?333?55?111?22?6\n
444?333?111?55?22?6\n
\n
444?555?666?2222?77?77?33?1\n
666?2222?444?555?77?77?33?1\n
2222?666?555?444?77?77?33?1\n

AC代码

#include<iostream>
using namespace std;
int n;
const int N = 1e5;
int a[N];
void shell_sort(int gap)
{
	for (int i = gap; i < n; i ++)//每一个元素
	{
		int t = a[i];
		int j;
		for (j = i - gap; j >= 0; j -= gap)
		{
			if (a[j] < t)
			{
				a[j + gap] = a[j];
			}
			else break;
		}
		a[j + gap] = t;
	}
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		cin >> n;
		for (int i = 0; i < n; i++)
		{
			cin >> a[i];
		}
		int gap = n;
		while (gap != 1)
		{
			gap /= 2;
			shell_sort(gap);
			for (int j = 0; j < n; j++)
			{
				cout << a[j];
				if (j != n - 1)cout << " ";
				else cout << endl;
			}
		}
		if (t)cout << endl;
	}
	return 0;
}

C. 冒泡排序

题目描述

给定一个包含从0到n-1各一次的数组，若使用冒泡排序将其排为升序，问其中需要进行多少次交换

输入

测试数据有多组，

每组由两行组成：第一行包含正整数n（n <= 5000）; 下一行包含从0到n-1的n个整数的序列。

输出

对于每组测试数据，

输出交换次数

样例查看模式?

正常显示查看格式

输入样例1?

10\n
1?3?6?9?0?8?5?7?4?2

输出样例1

22

AC代码

#include<iostream>
using namespace std;
int n;
const int N = 1e5;
int a[N];
void pop_sort()
{
	int ans = 0;
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (a[j] < a[i])swap(a[j], a[i]),ans++;
		}
	}
	cout << ans << endl;
}
int main()
{
	while (cin>>n)
	{
		for (int i = 0; i < n; i++)
		{
			cin >> a[i];
		}
		pop_sort();
	}
	return 0;
}

D. DS排序--快速排序

题目描述

给出一个数据序列，使用快速排序算法进行从小到大的排序

--程序要求--

若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio

程序中若include多过一个头文件，不看代码，作0分处理

不允许使用第三方对象或函数实现本题的要求

输入

第一行输入t，表示有t个测试示例
第二行输入n，表示第一个示例有n个数据
第三行输入n个数据，都是正整数，数据之间用空格隔开
以此类推

输出

每组测试数据，输出每趟快排的结果，即每次排好一个数字结果（长度为1的子序列，不用排，不用输出）。不同测试数据间用空行分隔。

样例查看模式?

正常显示查看格式

输入样例1?

2\n
6\n
111?22?6?444?333?55\n
8\n
77?555?33?1?444?77?666?2222\n

输出样例1

55?22?6?111?333?444\n
6?22?55?111?333?444\n
6?22?55?111?333?444\n
6?22?55?111?333?444\n
\n
1?33?77?555?444?77?666?2222\n
1?33?77?555?444?77?666?2222\n
1?33?77?77?444?555?666?2222\n
1?33?77?77?444?555?666?2222\n
1?33?77?77?444?555?666?2222\n

AC代码

#include<iostream>
using namespace std;
int n;
const int N = 1e5;
int a[N];
void quick_sort(int low, int high)
{
	int i = low, j = high;
	if (i >= j)return;
	int t = a[low];
	while (i != j)
	{
		while (a[j] >= t && i < j)j--;
		if (i >= j)break;
		a[i] = a[j];
		i++;
		while (a[i] <= t && i < j)i++;
		if (i < j)
		{
			swap(a[i], a[j]);
		}
	}
	a[i] = t;//重合
	for (int k= 1; k <= n; k++)
	{
		cout << a[k];
		if (k != n)cout << " ";
		else cout << endl;
	}
	quick_sort(low, i - 1);
	quick_sort(i + 1, high);
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
		}
		quick_sort(1, n);
      if(t)cout<<endl;
	}
	return 0;
}

?E. 大数据量的冒泡排序 (计次数)

题目描述

给定一个包含从0到n-1各一次的数组，若使用冒泡排序将其排为升序，问其中需要进行多少次交换

输入

测试数据有多组，

每组由两行组成：第一行包含正整数n（n <= 5000）; 下一行包含从0到n-1的n个整数的序列。

输出

对于每组测试数据，输出一行，输出交换总次数

样例查看模式?

正常显示查看格式

输入样例1?

10\n
1?3?6?9?0?8?5?7?4?2\n

输出样例1

22\n

AC代码

#include<iostream>
using namespace std;
int n;
const int N = 1e5;
int a[N];
void pop_sort()
{
	int ans = 0;
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (a[j] < a[i])swap(a[j], a[i]),ans++;
		}
	}
	cout << ans << endl;
}
int main()
{
	while (cin>>n)
	{
		for (int i = 0; i < n; i++)
		{
			cin >> a[i];
		}
		pop_sort();
	}
	return 0;
}

F. 与零交换

题目描述

将 { 0, 1, 2, ..., N-1 } 的任意一个排列进行排序并不困难，这里加一点难度，要求你只能通过一系列的 Swap(0, *) —— 即将一个数字与 0 交换 —— 的操作，将初始序列增序排列。例如对于初始序列 { 4, 0, 2, 1, 3 }，我们可以通过下列操作完成排序：

• Swap(0, 1)???{ 4, 1, 2, 0, 3 }
• Swap(0, 3)???{ 4, 1, 2, 3, 0 }
• Swap(0, 4)???{ 0, 1, 2, 3, 4 }

本题要求你找出将前 N 个非负整数的给定排列进行增序排序所需要的最少的与 0 交换的次数。

输入

输入在第一行给出正整数 N (≤105)；随后一行给出{ 0, 1, 2, ..., N-1 } 的一个排列。数字间以空格分隔。

输出

在一行中输出将给定序列进行增序排序所需要的最少的与 0 交换的次数。

样例查看模式?

正常显示查看格式

输入样例1?

10\n
3?5?7?2?6?4?9?0?8?1

输出样例1

9

AC代码

#include<iostream>
using namespace std;
int n;
const int N = 1e5;
int a[N];
bool st[N];
int ans;
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)cin >> a[i];
	for (int i = 0; i < n; i++)
	{
		if (!st[i] && a[i] != i)
		{
			bool flag = 0;
			int idx = i;
			int cnt = 0;
			while (!st[idx])
			{
				if (a[idx] == 0)flag = 1;
				st[idx] = 1;
				idx = a[idx];
				cnt++;
			}
			if (flag)ans += (cnt - 1);
			else ans += (cnt + 1);
		}
		else st[i] = 1;
	}
	cout << ans << endl;
	return 0;
}