排序算法

Question

给定数组arr[n],其中n=10000,0

Answer 1

采用一个类似于位图的结构来解决这个问题。首先，你的数据量不大，而且像你说的重复数目也不多，这里看作常数。可以声明一个10000字节大小的数组count[10000]，初始化为全0。扫描一遍你的待排序的数据，针对每一个值i，递增其对应的位置的数组值count[i]。扫描完毕后，再从头扫描一遍a[10000]，对于i，输出a[i]次即可。这样时间复杂度为O(n),
我js不怎么懂。勉强给你写个函数
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);