avatar
这个sort的复杂度# JobHunting - 待字闺中
c*a
1
我写了个类似counting sort的
public static int[] sort(int ar[], int n){
int[] buff = new int[n];
for(int i =0; ibuff[ar[i]]++;
int i=0,j=0;
int[]res = new int[ar.length];
while(jif(buff[j]>0){
res[i++] = j;
buff[j]--;
}
else j++;
}
return res;
}
感觉worst case,所以的elements都在同一个index,while loop走2n次...
这个是不是linear time O(n)
avatar
l*b
2
linear time也是指对于ar.length来说吧。。。这个n不是ar.length呀

【在 c*****a 的大作中提到】
: 我写了个类似counting sort的
: public static int[] sort(int ar[], int n){
: int[] buff = new int[n];
: for(int i =0; i: buff[ar[i]]++;
: int i=0,j=0;
: int[]res = new int[ar.length];
: while(j: if(buff[j]>0){
: res[i++] = j;

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。