这个sort的复杂度# JobHunting - 待字闺中
c*a
1 楼
我写了个类似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;
buff[j]--;
}
else j++;
}
return res;
}
感觉worst case,所以的elements都在同一个index,while loop走2n次...
这个是不是linear time O(n)
public static int[] sort(int ar[], int n){
int[] buff = new int[n];
for(int i =0; i
int i=0,j=0;
int[]res = new int[ar.length];
while(j
res[i++] = j;
buff[j]--;
}
else j++;
}
return res;
}
感觉worst case,所以的elements都在同一个index,while loop走2n次...
这个是不是linear time O(n)