P1177 题解

· · 题解

排序算法，想必各位都学过。

所以今天我来写一个比较经典的排序。

诶嘿

思路

由于本人是个蒟蒻，所以我们就来写选择排序吧！

选择排序的原理非常简单，就是双重循环，每次外循环遍历到第i个位置的时候，就在i到n的所有数里找最小值，然后他俩交换

举个栗子:

第一轮: a = [1, 1, 4, 5, 1, 4]

因为1已经是最小的，不变

第二轮:a = [1, 1, 4, 5, 1, 4]

第三轮:$a = [1, 1, 1, 5, 4, 4]

因为第三个位置的数4不是3到n里的最小值，所以4跟最小值1交换

第四轮:a = [1, 1, 1, 4, 5, 4]

因为第四个位置的数5不是4到n的最小值，所以与最小值交换

第五轮:a = [1, 1, 1, 4, 4, 5]

同上一轮

至此，选择排序结束，是不是非常的amazing

但是我们得考虑一下时间复杂度的问题，选择排序的复杂度很明显是O(n^2)，n最大10^5，容易TLE，所以我们要考虑优化一下选择排序

能优化的无非就是找最小值的那一步，我们来分析一下第二步干了什么:

  1. 求最小值下标，即维护最小值的下标
  2. 交换位置，即要能快速的动态修改和维护

所以就出现了一个非常不错的数据结构，叫做线段树,每次查询和修改都是O(log_2n)，10^5的数据完全够用

所以，我们的解就是选择排序+线段树维护，时间复杂度O(nlog_2n)

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
struct node
{
    int l, r, id;
}ST[N << 2];
int a[N], n, m;
inline void push_up(int ind)
{
    if(a[ST[ind*2].id] <= a[ST[ind*2+1].id])
        ST[ind].id = ST[ind*2].id;
    else
        ST[ind].id = ST[ind*2+1].id;
}
inline void build(int ind, int l, int r)
{
    ST[ind].l = l;
    ST[ind].r = r;
    if(l == r)
    {
        ST[ind].id = l;
        return;
    }
    int mid = (l+r)>>1;
    build(ind*2, l, mid);
    build(ind*2+1, mid+1, r);
    push_up(ind);
}
inline void upd(int ind, int x, int y)
{
    if(ST[ind].l == x && ST[ind].r == x)
    {
        ST[ind].id = y;
        return;
    }
    int mid = (ST[ind].l+ST[ind].r)>>1;
    if(x <= mid) upd(ind*2, x, y);
    if(x > mid) upd(ind*2+1, x, y);
    push_up(ind);
}
inline int ask(int ind, int tl, int tr)
{
    if(tl <= ST[ind].l && ST[ind].r <= tr)
        return ST[ind].id;
    int mid = (ST[ind].l+ST[ind].r)>>1, res = 0, i;
    if(tl <= mid)
    {
        i = ask(ind*2, tl, tr);
        if(a[i] < a[res])
            res = i;
    }
    if(tr > mid)
    {
        i = ask(ind*2+1, tl, tr);
        if(a[i] < a[res])
            res = i;
    }
    return res;
}
int main()
{
    cin >> n;
    for(int i = 1;i <= n;++i)
        scanf("%d", &a[i]);
    a[0] = 1e9;
    build(1, 1, n);
    for(int i = 1;i <= n;++i)
    {
        int j = ask(1, i, n);
        swap(a[i], a[j]);
        upd(1, i, i);
        upd(1, j, j);
    }
    for(int i = 1;i <= n;++i)
        cout << a[i] << " ";
    return 0;
}

注:还是写sort更有性价比，本文纯属单论选择排序优化，仅供参考