【题目链接】
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]);elsebreak;}}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]);elsebreak;}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完成交换。
-
-
如果要查询原数组第x元素
a[x]
在s数组中的下标,就是as[x]
。
【题解代码】
解法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);elsebreak;}}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);elsebreak;}}}else{cin >> x;cout << as[x] << endl;} }return 0;
}