作者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/cn.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