采用一個(gè)類(lèi)似于位圖的結(jié)構(gòu)來(lái)解決這個(gè)問(wèn)題。首先，你的數(shù)據(jù)量不大，而且像你說(shuō)的重復(fù)數(shù)目也不多，這里看作常數(shù)?？梢月暶饕粋€(gè)10000字節(jié)大小的數(shù)組count[10000]，初始化為全0。掃描一遍你的待排序的數(shù)據(jù)，針對(duì)每一個(gè)值i，遞增其對(duì)應(yīng)的位置的數(shù)組值count[i]。掃描完畢后，再?gòu)念^掃描一遍a[10000]，對(duì)于i，輸出a[i]次即可。這樣時(shí)間復(fù)雜度為O(n),
我js不怎么懂。勉強(qiáng)給你寫(xiě)個(gè)函數(shù)
functionmySort(arr,length){
varcount=newArray(length);
for(vari=0;i!=length;i++){
count[i]=0;
}
for(vari=0;i!=length;i++){
count[arr[i]]++;
}
varindex=0;
for(vari=0;i!=length;i++){
for(varj=0;jarr[index++]=i;
}
}
//alert(count);
}
//Anexample
vararr=newArray(10);
arr[0]=1;
arr[1]=2;
arr[2]=1;
arr[3]=0;
arr[4]=9;
arr[5]=8;
arr[6]=6;
arr[7]=2;
arr[8]=3;
arr[9]=6;
mySort(arr,10);
alert(arr);