题解 P1177 - 插入排序

yummy · 2024-08-27 10:56:13 · 题解

本文主要进行 STL 优化插入排序的讲解。如果想学习 O(n\log n) 等其他排序方法，请前往其他题解。

插入排序的基本流程如下：

假设我们有一个已经从小到大排好序的数组 a，我们现在要往 a 里面插入一个 x，并且仍然保持数组有序，怎么办呢？

为了让数组保持有序，我们需要以下面的方式插入：

• 寻找最前面的位置 i，使得 x\le a_i。此时因为 i 是最前面的位置，我们必然有 a_{i-1}\le x（若存在）。
• 将 x 插入在 a_i 前面。

第一个步骤我们可以使用 STL 中的 lower_bound 函数实现。lower_bound(first,last,value) 可以求出在 first 到 last（不包含 last）范围内第一个不小于 value 的位置。注意这里 first,last 都是迭代器或指针类型，返回的也是迭代器或指针。

本题中我们不妨使用 vector 对排好序的数组 a 进行存储。因为我们要查找整个 vector（从头到尾），所以要查找数字 x，可以使用 lower_bound(a.begin(),a.end(),x)。

在一个 vector 中，我们可以很方便地使用 insert 函数（或从 C++11 起可用 emplace 函数）进行插入，时间复杂度为插入位置到 vector 末尾的距离。emplace(pos,x); 可以在 pos 位置之前插入 x。

注意，虽然 lower_bound 函数使用二分查找，每次查找为 O(\log n) 的时间复杂度，但是 emplace 或 insert 的时间复杂度最坏 O(n)，因此整个程序时间复杂度还是 O(n^2)。所幸 emplace 或 insert 常数非常小，仍然可以通过这道题。

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> a;
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        auto it = lower_bound(a.begin(),a.end(),x);
        a.emplace(it,x);
    }
    for(int i=0;i<n;i++)
        cout<<a[i]<<' ';
    return 0;
}