作者Nt1 (用功点吧!)
看板CSSE
标题Re: [问题] 请教 exchange sort 演算法
时间Thu Mar 2 00:21:31 2006
※ 引述《Nt1 (用功点吧!)》之铭言：
我是一个要准备考试的考生，在看老师的讲义时有看到 exchange sort 演算法，是属於
stable 的演算法，但是我实际用手算了好多次，发现怎麽算都是 unstable …
请问一下，是我哪边算错了，还是 exchange sort 就是 unstable 的排序演算法呢？
code：
exchange_sort()
{
for (inti=0;i<size;i++){
for (int j=i+1,j<size;j++){
if(a[i]>a[j]) then swap(a[i],a[j]);
}
}
}
/*
一开始 a[0]和a[1]比，如果a[0]>a[1]，则互换，接着a[0]和a[2]比...
直到a[0]和a[n]比完。
再来a[1]和a[2]比……一直比到a[n-1]
*/
4,2,5,8,8+,6 (原始资料)
2,4,5,8,8+,6 (4>2，互换)
2,4,5,6,8+,8 (8>6，互换)
排完後，8 和 8+ 的位置不一样了，请问…这样不是应该是 unstable 吗？
可是我们老师的讲义上写 stable ，後面列的表格也是 satble，觉得很疑惑 @@
google 和学校图书馆都没什麽关於 exchange sort 的资料，我也知道它不重要…只是
一直有个疙瘩在心中~~~书都念不下去了~~请各位指正一下！是我关念有错还是讲义写错
谢谢！！
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.135.113.45
1F：推 hardcover:exchange sort(bubble sort): stable 03/01 22:50
2F：→ hardcover:selection sort: unstable 03/01 22:51
3F：→ hardcover:应该是这样 XD 03/01 22:51
我们老师的讲义是把 exchange sort 特别列一个演算法出来，然後 stability 的地方
是 stable，然後我看大部份的地方说 exchange sort包涵了 bubble sort，selection
sort…所以我找不到单独 exhcnage sort 的资料 @@" 只是自己按老师的演算法做是
unstable，和讲义不合@@"，让我很苦脑 >"<||||| 图书馆的书也没有一本有列出
exchange sort 这个演算法…也是只有说他包涵了哪几种这样。
好吧！我还是不要钻牛角尖了 XD 就当作没有这一个排序法吧
谢谢。
4F：推 edwar:(a[i]>a[j]) 改成 >= 呢? 03/01 23:22
唔…好像还是一样^^
谢谢。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.139.156.182