This topic has been archived. It cannot be replied.
-
工作学习 / IT技术讨论 / 请问如何这样SORT一个ARRAYLIST
-tongcd(Rock Your Body);
2004-7-1
{685}
(#1786302@0)
-
Don't stick to COMPARATOR any more. Using only COMPARATOR will not solve your problem for sure.
It's used for single 1-ary tree, but you are trying to apply it to multi non-1-ary trees.It should not be too hard to write your own algorithm and the complexity is about n*n.
-goes(goes);
2004-7-1
{86}
(#1786508@0)
-
thanks for reply. I know it has something to do with tree, but it is not exactly same as tree. Can you say more about the algorithm, please?
-tongcd(Rock Your Body);
2004-7-1
(#1786534@0)
-
Did your requirement cover this case? O1 and O2 are sibling. O3 is child of O1, O4 is child of O2. O3 and O4 do not have common children. what's the order of O3 and O4?
-goes(goes);
2004-7-1
(#1786638@0)
-
if o1 is sibling of o2, then it doesn't matter if o1 is listed before/after o2. if O3 is child of O1, O4 is child of O2. O3 and O4 do not have common children, then the order could be o1->o2->o3_o4 or o1->o2->o4->o3.In this case, the relative order of o1 and o2 doesn't matter, as long as they are all listed before o3,o4. Same, the relative order of o3,o4 is not import important as well.
Thanks
-tongcd(Rock Your Body);
2004-7-2
{182}
(#1786926@0)
-
So, from my understanding, any nodes with same root and same degree can be group together and the order between them is not important. The simplest algorithm in my mind will be, see if it works :
-goes(goes);
2004-7-2
{898}
(#1787075@0)
-
This is something I was thinking about. It looks ok except its compelxity. please read #1787443, thank you
-tongcd(Rock Your Body);
2004-7-2
(#1787446@0)
-
It is tree not array. so, use tree instead of array.
-ra_95(小人-生命换来的金钱);
2004-7-2
(#1786834@0)
-
yes, I know it looks quite like a tree instead of a 1-dimention array, butthere are may be more than 1 tree.
there could have orphaned node.
same child could have more than 1 parent and there are NO circular, which means the root node chould be more than 1.
Finally, to change everything into a tree would impact the existing code a lots, which is something I can't afford now.
thanks
-tongcd(Rock Your Body);
2004-7-2
{316}
(#1786927@0)
-
still use comparator la. 4 should be simple. 5 use a hui2shuo4; if we do not care performancea=o1
loop
a = a's dad
if it is o1 --> circle assert fails.
if it is o2; return o1<o2
end loop
-ra_95(小人-生命换来的金钱);
2004-7-2
{101}
(#1787215@0)
-
I re-visit my post, I didn't say it clearly. Please read #1787443, thank you.
-tongcd(Rock Your Body);
2004-7-2
(#1787449@0)
-
thanks goes and ra_95 for spending time help me solve this problem. I found solution from net.The sorting I am looking for is called topological sort or dag sorting. The attached reading says all.
-tongcd(Rock Your Body);
2004-7-2
(#1787443@0)