P1177【模板】排序 题解

· · 题解

题解区没有的 O (n^2) 做法

众所周知，插入排序的时间复杂度加上常数无法通过这道题目，那有没有优化的版本呢？

折半插入排序

二分查找的效率是很快的，为 O(\log n) 。那么将二分查找加进插入排序有怎样的效果呢？能达到 O(n\log{n})吗？

很遗憾，由于序列的插入，复杂度仍然是 O(n^2) ,看来只能接着优化常数了。

memmove是一样好用的函数，速度比for循环快，虽然时间复杂度还是 O(n) 。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[100005];
void Sort(int arr[], int len) {
    if (len<2)
        return;
    for (int i=1;i!=len+1;i++){
        int key=arr[i];
        int index=upper_bound(arr,arr+i,key)-arr;
        //神器1：upper_bound
        memmove(arr+index+1,arr+index,(i-index)*sizeof(int));
        //神器2：memmove
        arr[index]=key;
    }
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    Sort(a,n);
    for (int i=1;i<=n;i++)
        printf("%d ",a[i]);
    return 0;
}

时间复杂度见下表（常数极小） | 最好 | 最差 | 平均 | | :-----------: | :-----------: | :-----------: | | O(n\log n) | O(n^2) | O(n^2) |

传送门

参考资料：插入排序 - OI Wiki