神人排序-2.5条悟排序

Little | Chen

2026-10-11 21:51:57

发布于：浙江

10阅读

0回复

0点赞

基础介绍

排序复杂度： $O(^{2.5}_{2.5})$ （实则 $O(n)$ ）

排序原理：从后往前，高于后面的一直腰斩直到，直到不大于后一个

上代码

#include<bits/stdc++.h>
using namespace std;
int a[1000005],n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=n-1;i>=1;i--){
        while(a[i]>a[i+1])a[i]/=2;
    }
    for(int i=1;i<=n;i++)cout<<a[i]<<' ';
    return 0;
}