首页 > 代码库 > 100万个数据,数据值在0~65535之间,请用尽可能少的内存和最快的速度从小到大排序
100万个数据,数据值在0~65535之间,请用尽可能少的内存和最快的速度从小到大排序
场景说明:100万个数据,数据值在0~65535之间,请用尽可能少的内存和最快的速度从小到大排序
voidsort(int* array, int n)
{
//n的值在100万左右
//你的实现
}
我们首先观察到所有的数据已经保存到了array数组中,现在我们需要做的就是将数组中的元素排序。现在我们把数组中的元素提取出来比如是3,然后我们提取出数组下标是3的元素,保存到临时空间,通过负数来计算个数:
void sort(int* array, int n) { int tmp=0; for(int i=0;i<n;i++) { //如果遍历到当前是一个负数,表示是一个计数值(而不是一个排序值),遍历下一个 if(array[i]<0) { continue; } //遍历到的数值,作为下标的位置,取值是一个负数,表示这是一个计数值,--增加计数值,遍历下一个 if(array[array[i]]<0) { array[array[i]]--; continue; } //回溯到上一个值,重新开始匹配 tmp=array[array[i]]; array[array[i]]=-1; array[i]=tmp; i--; } }
100万个数据,数据值在0~65535之间,请用尽可能少的内存和最快的速度从小到大排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。