PTT數位生活區 / C_and_CPP (C/C++)

[問題] recursive---merge sort

看板C_and_CPP (C/C++)作者 (NI)時間16年前 (2009/07/03 17:52), 編輯推噓2(2推 0噓 8→)
留言10則, 4人參與, 最新討論串1/1
它的概念是說 我把一個大的矩陣弄成對半的兩個小矩陣去排 排完再把他們黏起來 然後那兩個對半的SORT也是在拆成兩個更小的這樣 可是我覺得非常的奇怪 因他的作法不就是說像這樣這樣嗎?這樣根本沒有辦法SORT阿 2 65 98 999 564 3 -3 57 變成 2 65 98 999 564 3 -3 57 然後再變成 2 65 98 999 564 3 -3 57 最後是 2 65 98 999 564 3 -3 57 這時候八個小矩陣很理所當然的 因為都只有一個ELEMENT 就是SORTED的了 接下來把它黏起來不是就變成 2 65 98 999 564 3 -3 57 阿不是根本就沒有排嗎? 而且依照他的概念好了 拆成兩個小的去SORT 變成 2 65 98 999 -3 3 57 564 阿然後黏起來 2 65 98 999 -3 3 57 564 這樣不是根本沒有排好嗎? 請各位大大們替我解答一下 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 125.233.146.73 ※ 編輯: flax00298 來自: 125.233.146.73 (07/03 17:53)
推
07/03 17:55, , 1F
「merge」並不是單純把兩個陣列「黏起來」
07/03 17:55, 1F
→
07/03 17:56, , 2F
而是在 linear time 內把它們合併成一個已排序的陣列
07/03 17:56, 2F
→
07/03 18:04, , 3F
對不起...I DONT GET IT...
07/03 18:04, 3F
→
07/03 18:04, , 4F
可以麻煩清楚一點嗎?還是這已經是最清楚了ˊˋ
07/03 18:04, 4F
→
07/03 18:18, , 5F
Merge的概念是把兩個sorted array合併成一個sorted array
07/03 18:18, 5F
→
07/03 18:19, , 6F
是沒錯~可是我不懂黏起來再牌還不是要排?
07/03 18:19, 6F
→
07/03 18:20, , 7F
這樣根直接排不就又變成一樣了...
07/03 18:20, 7F
→
07/03 18:22, , 8F
把兩個排好的合併成一個排好的 可以在linear time辦到
07/03 18:22, 8F
推
07/03 18:22, , 9F
不一樣, 比較的次數不一樣
07/03 18:22, 9F
→
07/03 18:24, , 10F
喔喔喔!!!我懂了~謝謝你們大家QQ
07/03 18:24, 10F
‣ 更多 flax00298 的文章
文章代碼(AID): #1AJTJn22 (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 flax00298 的文章
文章代碼(AID): #1AJTJn22 (C_and_CPP)