作者flax00298 (NI)
看板C_and_CPP
標題[新手][問題] recursive---merge sort
時間Fri Jul 3 17:52:48 2009
它的概念是說
我把一個大的矩陣弄成對半的兩個小矩陣去排
排完再把他們黏起來
然後那兩個對半的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)
1F：推 littleshan:「merge」並不是單純把兩個陣列「黏起來」 07/03 17:55
2F：→ littleshan:而是在 linear time 內把它們合併成一個已排序的陣列 07/03 17:56
3F：→ flax00298:對不起...I DONT GET IT... 07/03 18:04
4F：→ flax00298:可以麻煩清楚一點嗎?還是這已經是最清楚了ˊˋ 07/03 18:04
5F：→ kchiu:Merge的概念是把兩個sorted array合併成一個sorted array 07/03 18:18
6F：→ flax00298:是沒錯~可是我不懂黏起來再牌還不是要排? 07/03 18:19
7F：→ flax00298:這樣根直接排不就又變成一樣了... 07/03 18:20
8F：→ kchiu:把兩個排好的合併成一個排好的 可以在linear time辦到 07/03 18:22
9F：推 Ebergies:不一樣, 比較的次數不一樣 07/03 18:22
10F：→ flax00298:喔喔喔!!!我懂了~謝謝你們大家QQ 07/03 18:24