IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> PTA (乙级)1035 插入与归并 (25 分) -> 正文阅读

[数据结构与算法]PTA (乙级)1035 插入与归并 (25 分)

简单概括下题目意思,给定初始数组,在经过若干次排序后,判断该排序方式是插入或者是归并,并且输出下一次排序的结果。
解题思路
因为插入排序相对与归并更好判断,所以先判断是否是插入排序
判断方法如下:因为插入排序后半部分是不变的,假设数组在下标为 i i i的时候开始无序,那么从这个地方开始判断后半部分是否相同,如果后半部分相同,则是插入排序,否则是归并排序。归并排序需要知道当前归并子列的长度,通过判断子列间的有序型得出子列长度

原数组
4 2 1 3 13 14 12 11 8 9 7 6 10 5
排序后数组
1 2 3 4 11 12 13 14 6 7 8 9 5 10
通过前面的判断,该排序方式为归并排序,因为进行过若干次排序,则初始子列长度 ≥ \geq 2,则判断相邻子列的有序性,如2-3,跳过2*长度,12-13.以此类推,如果都满足有序,则将子列长度乘以2,直到条件不满足为止
AC代码如下

#include<cstdio>
using namespace std;
int a[110],b[110];
void Merge(int b[],int a[],int L,int R,int RightEnd) //归并排序
{
	int leftEnd=R-1;
	int Tmp=L;
	int start=L;
	while(L<=leftEnd&&R<=RightEnd)
	{
		if(b[L]<b[R]) a[Tmp++]=b[L++];
		else a[Tmp++]=b[R++];
	}
	while(L<=leftEnd) a[Tmp++]=b[L++];
	while(R<=RightEnd) a[Tmp++]=b[R++];
}
void Travers(int a[],int n)	//输出数组
{
	for(int i=0;i<n;i++)
	{
	printf("%d",a[i]);
	if(i!=n-1) printf(" ");
	}
	
}
int main()
{
	int n,p,p2;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	scanf("%d",&a[i]);
	for(int j=0;j<n;j++)
	scanf("%d",&b[j]);
	for(int i=1;i<n;i++)		//判断无序开始的位置
	{
		if(b[i]>=b[i-1]) continue;	//坑,没有等于号则测试点4无法通过
		else 
		{
		p=i;
		break;
		}
	}
	p2=p;
	while(p2<n)		//判断后续数组是否相同,
	{
		if(a[p2]==b[p2]) 
		{
			p2++;
		}
		else break;
	}
	if(p2==n)	//如果相同,那么是插入排序
	{
		printf("Insertion Sort\n");
		int j,Tmp=b[p];
		for(j=p;j>0&&b[j-1]>Tmp;j--)
		{
			b[j]=b[j-1];
		}
		b[j]=Tmp;
		Travers(b,n);
	}
	else{		//否则是归并排序
		printf("Merge Sort\n");
		bool flag=true;
		int length,k;
		for(length=2;length<=n;length*=2)
		{
			k=length;
			while(k<n)
			{
				if(b[k-1]<b[k])
				{
					k+=2*length;
				}else{
					flag=false;
					break;
				}
			}
			if(!flag) break;
		}		
		int i;
		for(i=0;i<=n-2*length;i+=length*2)
		{
			Merge(b,a,i,i+length,i+length*2-1);
		}
		if(i+length<n) Merge(b,a,i,i+length,n-1);
		else for(int j=i;j<n;j++) a[j]=b[j];
		Travers(a,n);
	}
	return 0;
}
  数据结构与算法 最新文章
二叉树lc题集
关于单链表及其常用操作的简单实现
二叉排序树(二叉搜索树)的算法实现
leetcode-python3-1759. 统计同构子字符串的
4.寻找两个正序数组的中位数
【leetcode】Nim 游戏c++
算法基础之贪心
LeetCode 2021-07-14
C++使用cuBLAS加速矩阵乘法运算
剑指offer - 调整数组顺序使奇数位于偶数前
上一篇文章           查看所有文章
加:2021-07-26 12:18:24  更:2021-07-26 12:21:02 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
360图书馆 购物 三丰科技 阅读网 日历 万年历 2021年9日历 -2021/9/27 3:20:41-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码