|
楼主 |
发表于 2003-12-14 19:08:50
|
显示全部楼层
嗯,斑竹说的是
最初由 libinary 发表
“C的“快速排序”是稳定的。也就是说,序列的相对位置不变。”
排序算法的“稳定”是指相同大小的项的相对位置不变,不同大小的项肯定要变,否则怎么排序?
比如序列里有3个25:
...25(1)...25(2)...25(3)...
排序以后3个25应该是相邻的,但是稳定的算法保证3个25的顺序和原序列一样:
...25(1)25(2)25(3)...
所以,要得到{1,200,0}这种结果就不能排序。
序列的顺序经算法处理后确实发生了变化,所谓的稳定的确也只是针对相同项而言,是我的错误。在此向各位兄弟道歉。
这个问题的解决办法,添加与原序列相对应的索引表,通对索引表对序列进行间接的快速排序,然后通过索引表间接地对序列的删除项赋值为标识-1。
这样序列的原来顺序就不变了,同时也保证了最优的时间复杂度,但添加了索引表,牺牲了空间。(其实,Perl的快速也是以牺牲内存空间为代价的;时间与空间,从来就难以两全其美,是吧)。 |
|