[問題] Space Merge Sortㄧ個觀念問題
最近要寫一個Space Merge Sort,但碰到了一個問題
講義上是有教學,但那排列前的數字實在是太完美了
所以我想說自己想一組數字看還會不會碰到額外的問題
我排的是9 6 2 3 5 8 7 4 13 15 12 11 1 10 14 16
因為有16個數字,所以分成4段
9 6 2 3 || 5 8 7 4 ||13 15 12 11 ||1 10 14 16
Step 1:先把最大的數字拉到第一段
16 15 14 13 || 5 8 7 4 || 3 6 10 11 || 1 12 2 9
Step 2:除了第一段之後的每段先各別排列
16 15 14 13 || 4 5 7 8 || 3 6 10 11 || 1 2 9 12
Step 3:除了第一段，取每段的最後一個值，依照這個值來排列每段的順序
因為二、三、四段分別是8 11 12，因為已經照順序，所以不用再排列了
Step 4:開始用指標來排列
o o o
16 15 14 13 || 4 5 7 8 || 3 6 10 11 || 1 2 9 12
o o o
3 15 14 13 || 4 5 7 8 || 16 6 10 11 || 1 2 9 12
o o o
3 4 14 13 || 15 5 7 8 || 16 6 10 11 || 1 2 9 12
o o o
3 4 5 13 || 15 14 7 8 || 16 6 10 11 || 1 2 9 12
o o o
3 4 5 6 || 15 14 7 8 || 16 6 10 11 || 1 2 9 12
。
。
。
。
。
。
從上面可發現第二、三段進行比較之後移到第一段
那1和2因為擺在第四段，所以排列後根本沒辦法移到第一段
那要怎樣排才會讓１和２排到第一段呢？以上就是我的問題了！
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.251.213.180
推
05/23 21:55, , 1F
05/23 21:55, 1F
→
05/23 21:56, , 2F
05/23 21:56, 2F
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章