【题目链接】
ybt 2075：【21CSPJ普及组】插入排序（sort）
洛谷 P7910 [CSP-J 2021] 插入排序
【题目考点】
1. 排序：
- 插入排序
插入排序示例：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, a[100005];
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> a[i];
for(int i = 2; i <= n; ++i)//将第i个数字插入有序序列
{
for(int j = i; j > 1; j--)//j指向待插入数字
{
if(a[j] < a[j - 1])
swap(a[j], a[j - 1]);
else
break;
}
}
for(int i = 1; i <= n; ++i)
cout << a[i] << ' ';
return 0;
}
- 索引排序
设原数组第i元素为a[i]，经过排序后的目标数组的第i元素为t[i]
索引数组ind：ind[i]表示t[i]在数组a中的下标。
即有目标数组第i元素t[i]为a[ind[i]]。
若要交换目标数组中两个元素swap(t[i], t[j])，索引数组的变化为swap(ind[i], ind[j])
实际上代码中不存在目标数组t，只保存索引数组ind。对索引数组进行排序，可以在不改变原数组a的情况下得到排序后的数组。
例：插入排序的索引排序
#include <bits/stdc++.h>
using namespace std;
#define N 100005
int main()
{
int n, a[N], ind[N];
cin >> n;
for(int i = 1; i <= n; ++i)
{
cin >> a[i];
ind[i] = i;//初始时t[i] == a[i]
}
for(int i = 2; i <= n; ++i)//将第i个数字插入有序序列
for(int j = i; j > 1; j--)//j指向待插入数字
{
if(a[ind[j]] < a[ind[j - 1]])
swap(ind[j], ind[j - 1]);
else
break;
}
for(int i = 1; i <= n; ++i)
cout << a[ind[i]] << ' ';
return 0;
}
【解题思路】
假想存在排序后的目标数组s，设数组sa为索引数组，表示sa[i]排序后下标i的元素s[i]在数组a中的下标。也就是s[i] == a[sa[i]]
设数组as，as[i]表示a[i]在排序后的s数组中的下标，也就是a[i] == s[as[i]]
当i为sa[i]时，有a[sa[i]] == s[as[sa[i]]] == s[i]，因此有as[sa[i]] == i。
sa与as保存的就是原数组a与目标数组s之间的两个方向的映射关系。
如果s[i]要与s[j]的值发生交换，那么就是从s[i] == a[sa[i]]同时s[j] == a[sa[j]]变为s[i] == a[sa[j]]同时s[j] == a[sa[i]]，只需要交换sa[i]与sa[j]的值即可。
而后根据as[sa[i]] == i，重新设as[sa[i]]与as[sa[j]]的值。因此要完成交换s[i]与s[j]，需要运行：
void Swap(int i, int j)
{
swap(sa[i], sa[j]);
as[sa[i]] = i;
as[sa[j]] = j;
}
主函数中，首先输入a数组，初始状态下s数组与a数组相同，满足s[i] == a[i]，因此有sa[i] = i; as[i] = i;。
先根据题意，使用索引数组完成插入排序，注意交换元素时需要使用我们定义的Swap函数。
而后进行q次操作
-
如果要改变元素，输入x，v。先将
a[x]变为v，而后观察a[x]是变大了还是变小了。-
如果满足
v > a[x]，变大了，则应该把a[x]对应在目标数组中的值s[as[x]]向后移动。
j从as[x]开始，不断变大，向后遍历s数组，直到j为n-1。
j向后移动的条件为：当前数字s[j]比后面的数字s[j+1]更大，或者在当前数字s[j]与后面数字s[j+1]相等的情况下，当前数字s[j]在原数组中的下标sa[j]比后面数字s[j+1]在原数组中的下标sa[j+1]更大。因为插入排序是稳定的排序，排序后相等数值元素的相对顺序不变。对于相同的数值，在原数组中下标更大的元素应该排在后面。
只要满足这一条件，就交换s[j]与s[j+1]，否则结束循环。该过程中的交换操作要使用我们定义的Swap函数，实际是由索引数组sa与as完成交换。 -
否则如果满足
v <= a[x]，变小了，则应该把a[x]对应在目标数组中的值s[as[x]]向前移动。
j从as[x]开始，不断变小，向前遍历s数组，直到j为2。
j向前移动的条件为：当前数字s[j]比前面的数字s[j-1]更小，或者在当前数字s[j]与前面数字s[j-1]相等的情况下，当前数字s[j]在原数组中的下标sa[j]比前面数字s[j-1]在原数组中的下标sa[j-1]更小。因为插入排序是稳定的排序，排序后相等数值元素的相对顺序不变。对于相同的数值，在原数组中下标更小的元素应该排在前面。
只要满足这一条件，就交换s[j]与s[j-1]，否则结束循环。该过程中的交换操作要使用我们定义的Swap函数，实际是由索引数组sa与as完成交换。文章来源：https://www.toymoban.com/news/detail-730302.html
-
-
如果要查询原数组第x元素
a[x]在s数组中的下标，就是as[x]。文章来源地址https://www.toymoban.com/news/detail-730302.html
【题解代码】
解法1：
#include<bits/stdc++.h>
using namespace std;
#define N 8005
int a[N];
int sa[N];//sa[i]:排序后下标i的元素在数组a中的下标
int as[N];//as[i]:a[i]在排序后的下标
void Swap(int i, int j)
{//排序后第i元素第j元素交换
swap(sa[i], sa[j]);
as[sa[i]] = i;
as[sa[j]] = j;
}
int main()
{
int n, q, t, x, v, px;
cin >> n >> q;
for(int i = 1; i <= n; ++i)
{
cin >> a[i];
sa[i] = i;
as[i] = i;
}
for(int i = 1; i <= n; ++i)
for(int j = i; j >= 2; --j)
if(a[sa[j]] < a[sa[j-1]])
Swap(j, j-1);
for(int i = 1; i <= q; ++i)
{//由于插入排序是稳定的，如相等，下标大的在右边
cin >> t;
if(t == 1)
{
cin >> x >> v;
if(v > a[x])//变大，a[x]右移
{
a[x] = v;
for(int j = as[x]; j <= n - 1; ++j)
{
if(a[sa[j]] > a[sa[j+1]] || a[sa[j]] == a[sa[j+1]] && sa[j] > sa[j+1])
Swap(j, j+1);
else
break;
}
}
else
{//变小，a[x]左移
a[x] = v;
for(int j = as[x]; j >= 2; --j)
{
if(a[sa[j]] < a[sa[j-1]] || a[sa[j]] == a[sa[j-1]] && sa[j] < sa[j-1])
Swap(j, j-1);
else
break;
}
}
}
else
{
cin >> x;
cout << as[x] << endl;
}
}
return 0;
}
到了这里，关于信息学奥赛一本通 2075：【21CSPJ普及组】插入排序（sort） | 洛谷 P7910 [CSP-J 2021] 插入排序的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
