大数组排序的最好解决办法?
来源:百度知道 编辑:UC知道 时间:2024/05/16 14:07:04
一个二维 数组 [2][100000 * 400000] =
{
{1,500000},{2,499000},{3,498900}....
}
类似于一个表 两个列 其中一个列是 用户的id 另一个列是 用户的某一个游戏的得分
需求来了:
新用户注册 积分需要插入 完成后要进行排序(排名)
老用户打了新的得分 也许是比原来高的成绩 也许没有原来高
如果比原来高 就替换原来的成绩 完成后要进行排序(排名)
用C#语言 写一段程序 要求最高效率的在最短时间内实现 插入一条新纪录并且排序 数组大小 [21亿]
如果给的效率高 可以继续追加分数!
直接用数据库排序就好了 比其他的效率高多了
这么大的数据量,为什么不使用网络数据库?所有的这些操作在数据库中是非常简单的。
你可以采用AVL二叉平衡排序树进行你的操作。。这个是目前为止耗时最少的动态维护数组方式(当然,如果你喜欢SBT也可以。。但是SBT的C我不会。。)!
这里附上AVL树的经典C的标程,{main}是测试数据,你可以把它改成文件流就可以了。。
typedef struct avl{
int fact;
struct avl *lc;
struct avl *rc;
int data;
}*avl;
int insertAVL(avl *r,int e,int *taller)
{
avl bak = *r;
if(!*r)
{
*r = (avl)malloc(sizeof(struct avl));
(*r)->lc = (*r)->rc = 0;
(*r)->fact = 0;
(*r)->data = e;
*taller = 1;
}else{
if((*r)->data==e){*taller = 0;return 0;}
if(e<(*r)->data)
{
if(!insertAVL(&(*r)->lc,e,taller))return 0;
if(*taller)
{
switch(bak->fact)
{
case 1: ajust_Left(r);*