作者NOtWorThy ()
看板Grad-ProbAsk
标题Re: [理工] [资结]-sort
时间Wed Dec 16 00:03:15 2009
※ 引述《NOtWorThy ()》之铭言：
请问一下 为何Insertion sort是stable?
或者其他sort eq.bubble selection ...etc
我在想答案没有一定吧?!
要是我在条件判断式里面把"<"改成"<="(or 反之)
就可能改变她是否stable 不是?!
因为这些都是在compare base底下
烦请高手 赐教
谢谢
ex. 我把判断改成
while a[j]>=InsertData
a[j+1] <- a[j]
j <- j-1
(1 2 3 4 5 6 7 8 ) 5'
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
=> 1 2 3 4 5' 5 6 7 8
这样不就变Unstable了??
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.116.218.120
1F：推 tryPTT:答案一定的喔 你可以用几个数字(包含相同key)代一下就知了 12/15 23:53
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.116.218.120
2F：推 tryPTT:如果你改成=就会变unstable没错，不过这样就变多此一举了。 12/16 00:09
3F：→ NOtWorThy:那考试出来是要怎麽办阿= = 谁知她演算法怎写?! 12/16 00:14
4F：推 converse2006:请翻圣经本 里面自然会跟你说为什麽 12/16 00:53
5F：→ converse2006:看不懂英文就直接看CODE C的版本很好懂 12/16 00:53
6F：推 tsarnfeng:你的想法没错 但是 规则是人订的我们只是遵从的人 12/16 01:45
7F：→ tsarnfeng:不是创始者 12/16 01:45
8F：→ ssccg:可以写成stable的就是stable，不能的才会说是unstable 12/16 05:51
9F：推 polomoss:能有更好的演算法可以是stable，为何硬要写成unstable 12/16 11:02
10F：→ polomoss:而那些unstable是没办法改尽到stable才称unstable 12/16 11:02