[問題] Wiki 的合併排序法
這個連結是中文維基百科的合併排序法
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://www.ptt.cc/bbs/java/M.1481845143.A.7D3.html
→
12/16 09:11, , 1F
12/16 09:11, 1F
為何要加入交換的步驟, 讓 result 和 arr 不是指向相同的參考嗎 ?
※ 編輯: obelisk0114 (169.235.208.129), 12/16/2016 09:33:45
→
12/16 10:04, , 2F
12/16 10:04, 2F
→
12/16 10:05, , 3F
12/16 10:05, 3F
→
12/16 10:06, , 4F
12/16 10:06, 4F
我把交換指向註解掉,結果會錯誤
假如只是為了利用現有空間,應該沒有問題
→
12/16 10:07, , 5F
12/16 10:07, 5F
→
12/16 10:09, , 6F
12/16 10:09, 6F
→
12/16 10:10, , 7F
12/16 10:10, 7F
這樣 start + break 就會等於 len
應該是不會有大於 len 的情形吧
※ 編輯: obelisk0114 (169.235.208.129), 12/16/2016 10:43:14
→
12/16 10:47, , 8F
12/16 10:47, 8F
→
12/16 10:47, , 9F
12/16 10:47, 9F
→
12/16 10:56, , 10F
12/16 10:56, 10F
→
12/16 10:58, , 11F
12/16 10:58, 11F
→
12/16 11:00, , 12F
12/16 11:00, 12F
→
12/16 11:00, , 13F
12/16 11:00, 13F
→
12/16 11:01, , 14F
12/16 11:01, 14F
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
→
12/16 13:14, , 15F
12/16 13:14, 15F
→
12/16 13:14, , 16F
12/16 13:14, 16F
→
12/16 19:02, , 17F
12/16 19:02, 17F
java 近期熱門文章
PTT數位生活區 即時熱門文章
