#代码阅读 求证明
2026-02-03 08:17:07
发布于：上海
32阅读
0回复
0点赞
null
有没有大佬能够帮我看看下面这段代码是否能够完成排序工作？
如果能够完成排序，那么它的原理是什么？时间复杂度是多少？
如果不能，求一组反例。
#include<iostream>
using namespace std;
int flog(int n,int base=2){
if(!n)return -1;
int s=1,t=0;
while(s<=n)s*=base,t++;
return --t;
}
int power(int n,int base=2){
if(n<0)return -1;
int s=1,t=0;
while(t++<n)s*=base;
return s;
}
void swap(int&a,int&b){
int t=a;
a=b;
b=t;
}
//外循环i=[1,power(flog(n-1)))，
//内循环j=[1,n-power(flog(n)-flog(i))]
//读入区间为[1,n]
const int N=1e4;
int n,s[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>s[i];
int u=power(flog(n-1)+1);
for(int i=1;i<u;i++){
bool ok=1;//不交换判断的优化
int m=power(flog(n-1)-flog(i));
//解释这里的flog：由于这里当n为2的k次方时是无法选中一段距离使得起始下标和终止下标差为2的k次方的，
//因此，这里需要将n作减少1的处理才能够保证下标不越界；
//当n为1的时候，i循环for条件中，i=1作为初始值且i<1作为执行条件，故不调用flog(0)（flog(n)中的n一定大于0）
for(int j=1;j<=n-m;j++){
if(s[j]>s[j+m]){
swap(s[j],s[j+m]);
ok=0;
}
}
if(ok)i=power(flog(i)+1)-1;
}
for(int i=1;i<=n;i++)cout<<s[i]<<" ";
return 0;
}
有帮助，赞一个