排序算法请教

Real197

现在有一个排名榜单的需求，根据用户的积分进行排名，其中用户的积分是经常变化的。
要求：
1、排名结果是实时的，即用户积分变化后，相应的名次也该立即相关变化。
2、可以根据排名查到用户的积分。
3、根据用户信息查到用户的排名。

现在觉得比较困难的地方就是积分变化后，怎么做到高效率的排名变化。

自己想的一个算法，只是无法做到高效率。
算法：
1、用一个一维指针数组（int* A[MAX]）来实现用户的排名及根据排名查询用户的信息。数组的下标就是用户的排名，数组元素的值就是用户信息的入口地址。
2、假设需求3已经完成（虽然效率不高），即每个用户的排名已知。
3、用户M的积分有变化，根据其原来排名n，用其新积分跟第n-1，n-2，……，n-i名的积分进行比较，直到找到其最后的新排名n-k。
4、记录原数组第n元素到中间变量，然后执行memmove（&A[n], &A[n-1],k+2）把第n-1到n-k的用户都往下移一个名次，恢复中间变量到第n-k名字实现用户M名次的变化。
5、修改原第n到第n-k用户的名次(这一步需要遍历获取到用户信息地址后，再一个一个修改，如果这中间的用户数多的话，那效率非常低)。

以上算法是对原有数组中用户排名变化，如果有心用户需要新添加到该数据，需要一个一个从头到尾遍历到合适的位置，然后再采用memmove实现各个用户排名的变更。

上面的方面肯定不是好方法，不知大家有没有什么更好的算法。

lenky0401

不用修改名次 甚至根本不需要记录元素对应的名次 因此数组已经隐含的包含了名次信息 直接拿当前元素的地址减去首元素的地址除以sizeof(int)就是它的对应名次

lenky0401

如果不要移动数据 那你就不要用数组 用链表更好 此时就需要记录各元素对应的名次

Real197

原帖由 lenky0401 于 2009-4-16 16:26 发表
不用修改名次 甚至根本不需要记录元素对应的名次 因此数组已经隐含的包含了名次信息 直接拿当前元素的地址减去首元素的地址除以sizeof(int)就是它的对应名次

非常好的方法，赞！！！

Real197

原帖由 lenky0401 于 2009-4-16 16:27 发表
如果不要移动数据 那你就不要用数组 用链表更好 此时就需要记录各元素对应的名次

用链表不行，涉及到积分修改时，很难进行迁移
而且查找某个名次的用户时更麻烦，需要遍历链表，这效率就很低了。

songtebo

用数组可以就可以了，有新用户需要新添加到该数据不怕，一开始总在最后：）

emacsnw

Fibonacci heap的一个典型应用。。。

daybreakcx

看你的要求是根据积分进行排序，并且是实时的，想来想去也我所知道有红黑树+HASH可以满足你的要求。
对于你的用户信息，你可以一维线性存储（就是简单一维数组），那么对于积分构造一个红黑树，一个节点对应一个用户的信息，同时为了方便，这样红黑树的信息中存储着其左孩子和右孩子的个数（当然AVL也可以，这里关键对于排序利用了二叉查找树，用红黑树和AVL只是因为他们是更好的实现，树的高度低减少复杂度），当然左孩子的个数就是他的排名（二叉查找树中一个节点的左子树上存放的都是比他小的节点）。
当然，红黑树中节点只是单纯的存放积分而不完整存放节点的整个信息（只有用户信息的索引下标也就是一维数组的坐标），这样积分的修改和通过排名查找用户的时间复杂度就是O(logn)了（n为当前节点数）。
至于你所说的根据用户信息查到排名，最直接的方法是直接一维索引，但是这样的速度偏慢，复杂度是O(n)的，为此，我们引入HASH，这样可以在O(1)时间内找到用户名对应信息的数组下标。
总的说来就是除了原先的一维数组存放信息外附加两个结构，一个是红黑树，用来做排名记录和积分排序，另一个是HASH表，用来做通过用户名查找用户信息位置。

action08

原帖由 daybreakcx 于 2009-4-17 07:08 发表
看你的要求是根据积分进行排序，并且是实时的，想来想去也我所知道有红黑树+HASH可以满足你的要求。
对于你的用户信息，你可以一维线性存储（就是简单一维数组），那么对于积分构造一个红黑树，一个节点对应一 ...

红黑树是不是性能差于二叉树的？

PS，数据结构的很多概念都的不记得了

suyixi

用hash啊，这样速度快，而且又是操作链表