作者obelisk0114 (追風箏的孩子)
看板java
標題[問題] Wiki 的合併排序法
時間Fri Dec 16 07:38:56 2016
這個連結是中文維基百科的合併排序法
https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F
在 java 的疊代版程式如下
public static void merge_sort(int[] arr) {
int len = arr.length;
int[] result = new int[len];
int block, start;
// 原版代码的迭代次数少了一次，没有考虑到奇数列数组的情况
for(block = 1; block < len*2; block *= 2) {
for(start = 0; start <len; start += 2 * block) {
int low = start;
int mid = (start + block) < len ? (start + block) : len;
int high = (start + 2 * block) < len ? (start + 2 * block) : len;
//两个块的起始下标及结束下标
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
//开始对两个block进行归并排序
while (start1 < end1 && start2 < end2) {
result[low++] = arr[start1] < arr[start2] ? arr[start1++] :
arr[start2++];
}
while(start1 < end1) {
result[low++] = arr[start1++];
}
while(start2 < end2) {
result[low++] = arr[start2++];
}
}
int[] temp = arr;
arr = result;
result = temp;
}
result = arr;
}
------------------
這個程式看起來應該是使用 bottom-up 來實作
但是他有幾個地方我有點疑問
1. for(block = 1; block < len*2; block *= 2)
我覺得 block < len 好像就可以了 ?
2. int mid = (start + block) < len ? (start + block) : len;
mid 只有在只剩單一元素時才會 >= len,但是只剩單一元素也不需做比較
所以好像不需要判斷 ?
3.
int[] temp = arr;
arr = result;
result = temp;
一開始我想就是把結果存回去,用
for (int i = 0; i < arr.length; i++) {
arr[i] = result[i];
}
但是他卻用淺層複製做交換
為何要用淺層複製來做交換 ? 速度會比較快嗎 ?
--
肝不好 ▁▁ ● ◤
肝若好
人生是黑白的 ▏ ◤
考卷是空白的
▏ ◤
、 ﹐
● ●b 囧 ▎ ●> ● ◤
▌ ﹍﹍ ０ ▊囧＞
幹...
▲ ■┘ ■ ▎ ■ █◤ ▌ ㄏ▋ ︶■
〈﹀ ∥ ▁▁∥ ▎ ﹀〉◤
▋ ▊ 〈\
ψcockroach727
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 71.95.52.50
※ 文章網址: https://webptt.com/m.aspx?n=bbs/java/M.1481845143.A.7D3.html
1F：→ ssccg: 3當然比較快啊，每次loop少copy整個array一次 12/16 09:11
為何要加入交換的步驟, 讓 result 和 arr 不是指向相同的參考嗎 ?
※ 編輯: obelisk0114 (169.235.208.129), 12/16/2016 09:33:45
2F：→ ssccg: loop裡都是從來源arr到目標result，做完一次當然要把來源改 12/16 10:04
3F：→ ssccg: 成指向這輪的結果(arr=result)，至於result=temp(arr)只是 12/16 10:05
4F：→ ssccg: 重新利用現有空間而已 12/16 10:06
我把交換指向註解掉,結果會錯誤
假如只是為了利用現有空間,應該沒有問題
5F：→ ssccg: 另外這不是淺層複製，根本沒有複製，是交換指向的array物件 12/16 10:07
6F：→ ssccg: 1沒錯到block < len就可 12/16 10:09
7F：→ ssccg: 2 當然還是要判斷只是不用多做只剩一個block直接break就好 12/16 10:10
這樣 start + break 就會等於 len
應該是不會有大於 len 的情形吧
※ 編輯: obelisk0114 (169.235.208.129), 12/16/2016 10:43:14
8F：→ ssccg: 當然會錯誤啊，不利用現有空間不是不用做事 12/16 10:47
9F：→ ssccg: 是要像一開始那樣result = new int[len]; 12/16 10:47
10F：→ ssccg: 然後你的等於大於len我看不懂你是要說什麼... 12/16 10:56
11F：→ ssccg: 我是說start + block < len這判斷一定要做，當這條件不成立 12/16 10:58
12F：→ ssccg: (start + block >= len)時，代表這輪的兩個block中後面那個 12/16 11:00
13F：→ ssccg: 沒有了，只有一個block，至於是>還是=是差在前面那個block 12/16 11:00
14F：→ ssccg: 大小是不是剛好等於這輪的block，跟要不要這判斷沒關係 12/16 11:01
int mid = (start + block) < len ? (start + block) : len;
是不是只需要寫成這樣就好 ?
int mid = start + block
會出現 mid 大於 len 的情形嗎 ?
※ 編輯: obelisk0114 (169.235.208.129), 12/16/2016 11:06:21
15F：→ ssccg: 舉例來說block = 2, start = 4, len = 5 12/16 13:14
16F：→ ssccg: 至少要加 if (mid >= len) break; 12/16 13:14
17F：→ obelisk0114: 了解了, Thanks 12/16 19:02