[理工] [資結] Quick sort 資料中有相同鍵值如何排序?

看板Grad-ProbAsk作者 (帥氣的)時間15年前 (2011/02/25 19:17), 編輯推噓3(3推 0噓 7→)
留言10則, 4人參與, 最新討論串1/1
請教各位 使用Quick sort排序這一段數列 10 1 5 26 12 23 10* 第一回後的結果是 A. 10*,1,5,10,12,23,26 還是 B. 5,1,10,26,12,23,10* 這一題的資料中有相同鍵值,且剛好是做為pivot key 我自己照著演算法排是 A,但題庫給的答案卻是 B 麻煩各位同學,幫我解答一下了,謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.171.30.243
推
02/25 19:33, , 1F
B看起來是 Left pivot如果 小於 就繼續 ; Right 採大於
02/25 19:33, 1F
→
02/25 19:34, , 2F
所以一開始Left pivot 10<10 = False 就停下來了
02/25 19:34, 2F
→
02/25 19:35, , 3F
所以Left pivot指向1th ; Right pivot指向3th元素 再交換
02/25 19:35, 3F
推
02/25 19:48, , 4F
我記得是小於等於跟大於等於耶，我算出來也是A
02/25 19:48, 4F
推
02/25 19:58, , 5F
我覺得是看演算法的小細節是怎樣決定怎麼排 考試就照書..
02/25 19:58, 5F
→
02/25 20:02, , 6F
其實這兩種最後排起來差不多 只差在Stable or not
02/25 20:02, 6F
→
02/25 20:03, , 7F
至於到底是 小於等於+大於 還是 另一種 我也不知道
02/25 20:03, 7F
→
02/25 20:04, , 8F
所以我上面說的是 B"看起來"的作法
02/25 20:04, 8F
→
02/26 12:41, , 9F
謝謝各位的回覆.A和B應該是採用不同的Algo.所以結果不同
02/26 12:41, 9F
→
02/26 12:44, , 10F
但一樣都是Quick sort的概念
02/26 12:44, 10F
‣ 更多 leewin 的文章
文章代碼(AID): #1DPu_F6i (Grad-ProbAsk)