c*****a
发帖数: 808 | 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) | l*******b
发帖数: 2586 | 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;
|
|
