【CSP-J 2021】插入排序

skystars

这是我们上次竞赛的T2，难度一般，最近我深入研究了一下排序算法，发现中间可以不用sort进行排序，可以使用类似冒泡排序的算法进行排序

代码如下：

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
struct node { // x存放一开始的位置，v存放值
    int v, x;
};
inline int read() { // 读入优化
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
bool cmp(node a, node b) {
    return a.v < b.v;
}
node a[8005];
int x;
int main() {
    int n, q;
    n = read();
    q = read();
    for (int i = 1; i <= n; i++) a[i].v = read(), a[i].x = i;
    stable_sort(a + 1, a + 1 + n, cmp); // 先排一遍序
    // stable_sort 是 STL 中的稳定排序
    for (int i = 1; i <= q; i++) {
        int c;
        c = read();
        if (c == 1) {
            int v;
            x = read();
            v = read();
            for (int i = 1; i <= n; i++) {
                if (a[i].x == x) { // 循环查找，找到x在有序数组中的位置
                    a[i].v = v; // 修改值
                    // 冒泡排序，将该项放入正确的位置
                    while (a[i].v < a[i - 1].v && i != 1)
                        swap(a[i], a[i - 1]), i--;
                    while (a[i].v > a[i + 1].v && i != n)
                        swap(a[i], a[i + 1]), i++;
                    while (a[i].v == a[i - 1].v && a[i].x < a[i - 1].x) // 处理相等的情况
                        swap(a[i], a[i - 1]), i--;
                    while (a[i].v == a[i + 1].v && a[i].x > a[i + 1].x)
                        swap(a[i], a[i + 1]), i++;
                    break; // 跳出循环
                }
            }
            // sort(a + 1, a + 1 + n, cmp); // 不需要使用sort对整个数组进行排序
        }
        else if (c == 2) {
            x = read();
            for (int i = 1; i <= n; i++) {
                if (a[i].x == x) { // // 循环查找，找到x在有序数组中的位置
                    printf("%d\n", i); // 输出
                    break; // 跳出循环
                }
            }
        }
    }
    return 0;
}