2021JSP普及组第二题：插入排序

2021JSP普及组第二题
题目：

思路：
题目要求排序后根据操作进行对应操作。

• 操作一需要显示某位置数据排序后的位置，所以需要定义结构体数组储存原数据的位置和数据本身
• 排序后所得数据要根据原位置输出排序后的位置，所以建立一个新的数组，数组下标对应数据原位置，值则为排序后的位置
• 第一部可以直接sort排序，但是操作后如果都用sort会超时。题干的插入排序不难想到，插入排序即是对已经排好序的数组进行插入操作后排序，一次插入后排序的复杂度为o(2n)
  1. 思路一：可以考虑判断操作的位置前后的数据大小，然后对数组前一段进行修改，或者后一段进行修改。但是由于相同数据还要判断数据原位置的大小，所以考虑的过程相对复杂
  2. 思路二：可以直接判断整个数组的内容，正着遍历和反着遍历（遍历是只能判断相邻两个元素的大小，所以反着再遍历一遍才能保持排序准确），而数据相同需要判断原位置大小（插入排序中，若数据相同，数据排序后的相对位置是不变的）
• 排序过程是对结构体进行排序，因此排序函数需要指针，而不是简单的形参

//定义结构体用来存储数组值和下标
//排序可以直接用sort
//修改后的数据修直接遍历处理 
#include<bits/stdc++.h>
#include <algorithm> 
using namespace std;struct node{int n;int id;}arr[8001]; 
void swap(node *a,node *b);
bool cmp(node a, node b){if(a.n!=b.n) return a.n<b.n;//升序排列 else return a.id<b.id;
}
int main(){int arr_k,k,b[8005];//分别储存数组长度，操作数int k1,m,m1,m2;//分别储存操作序号和数据 cin>>arr_k>>k;for(int i=1;i<=arr_k;i++){cin>>arr[i].n;arr[i].id=i;}sort(arr,arr+arr_k+1,cmp);//排序 //记录排序后的数据for(int i=1;i<=arr_k;i++){b[arr[i].id]=i;} while(k--){cin>>k1;if(k1==2){cin>>m;cout<<b[m]<<endl;}else{cin>>m1>>m2;arr[b[m1]].n=m2;arr[b[m1]].id=m1;for(int i=1;i<arr_k;i++){ if(cmp(arr[i],arr[i+1])==0){swap(&arr[i],&arr[i+1]);}for(int i=arr_k;i>1;i--){  if(cmp(arr[i-1],arr[i])==0){swap(&arr[i],&arr[i-1]);}}//更新排序for(int i=1;i<=arr_k;i++){b[arr[i].id]=i;} }}return 0;
}
void swap(node *a,node *b){int t1,t2;t1=a->n,t2=a->id;a->n=b->n,a->id=b->id;b->n=t1,b->id=t2;
}