排序算法

给定数组arr[n],其中n=10000,0已知数组中的值时乱序的,且其值均匀分布在0-9999区间,只有少量数值重复
请用js代码写一个函数,以最快的方式完成对该数组的升序排序,要求算法时间复杂度必须小于O(NLOG2N).
ABOUTYOU
浏览 418回答 2
2回答

皈依舞

采用一个类似于位图的结构来解决这个问题。首先,你的数据量不大,而且像你说的重复数目也不多,这里看作常数。可以声明一个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;j
打开App,查看更多内容
随时随地看视频慕课网APP

相关分类

JavaScript