首页 > 代码库 > 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之间,请用尽可能少的内存和最快的速度从小到大排序