您所在位置：主题：基于归并的链表排序猜想
euc
[专家分：4310] 发布于 2006-04-06 07:12:00
一个待排序(增)的链表,可以按递增的方向把它分成若干段,例如元素排列:
6->11->1->7->3->8->4->5->NULL, 可分段成:
6->11->NULL, 1->7->NULL, 3->8->NULL, 4->5->NULL, 然后组合:
4->5->6->11->NULL, 1->7->NULL, 3->8->NULL.
最后对三段做两次merge()即可.
这个方法的困难在于如何高效率地把几个段重新组合. 举例,一个最简陋的实现策略:
遍历一次, 每一段只和第一段做组合, 然后归并.
再优化些的:
在遍历中,若当前块不能和数组记录的每个块归并,加入数组;
否则在数组中选一个最合适的块做组合.(问题在于数组的大小怎么定)
6->11->1->7->3->8->4->5->NULL, 可分段成:
6->11->NULL, 1->7->NULL, 3->8->NULL, 4->5->NULL, 然后组合:
4->5->6->11->NULL, 1->7->NULL, 3->8->NULL.
最后对三段做两次merge()即可.
这个方法的困难在于如何高效率地把几个段重新组合. 举例,一个最简陋的实现策略:
遍历一次, 每一段只和第一段做组合, 然后归并.
再优化些的:
在遍历中,若当前块不能和数组记录的每个块归并,加入数组;
否则在数组中选一个最合适的块做组合.(问题在于数组的大小怎么定)
