作者KAINTS (Faith)
看板Programming
标题[问题] MergeSort内实作sort可以用别的sort吗?
时间Sun Apr 4 21:00:03 2021
请问各位大大好最近小弟在写一些sort的练习
我想请教一下 MergeSort内分为两个阶段
1.Divide (分割)
2.Conquer (合并)
小弟在写合并的时候
有一个问题觉得困惑
因为conquer时必须要把序列sort过
那麽我在这个时候去调用别的sort这样也可以吗?
比方说我sort的方式是用quick sort
这样会影响这个演算法本身的时间复杂度?
我的认知是不会 毕竟我们都已经经过divied的了
所以基本上就是O(logn)
不知道我这样理解对吗?
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 122.116.222.216 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Programming/M.1617541205.A.B5C.html
1F：推 alan23273850: mergesort 精华就是可以一直 divid 111.83.155.49 04/05 00:48
2F：→ alan23273850: e，如果还要调用其他 sort 的话那 111.83.155.49 04/05 00:48
3F：→ alan23273850: 干嘛还要 divide 111.83.155.49 04/05 00:48
4F：→ alan23273850: 你时间当然就是 qs(n/2) + O(n) 111.83.155.49 04/05 00:50
5F：→ alan23273850: 更正，2 * qs(n/2) + O(n) 111.83.155.49 04/05 00:51
6F：推 LPH66: 这里有个概念叫做递回, 你分割後得到了两个 180.177.0.237 04/05 01:02
7F：→ LPH66: 同样需要排序但数量变少的阵列 180.177.0.237 04/05 01:02
8F：→ LPH66: 那你就可以递回呼叫自己进行排序 180.177.0.237 04/05 01:03
9F：→ LPH66: 数量变少这个条件会保证你能切到剩一个 180.177.0.237 04/05 01:03
10F：→ LPH66: ==== 180.177.0.237 04/05 01:06
11F：→ LPH66: 但是, 如果你的焦点只想摆在合并步骤的话 180.177.0.237 04/05 01:06
12F：→ LPH66: 你已经不是在用合并排序法, 而只是单纯地 180.177.0.237 04/05 01:07
13F：→ LPH66: 把两个已排序的阵列合成一个排序阵列 180.177.0.237 04/05 01:07
14F：→ LPH66: 合并排序法需要这个合并步骤但这不是全部 180.177.0.237 04/05 01:07
感谢两位大大指导
但我是已经确定把分割做到最後了只剩一个
我只是想说在合并的时候使用While去合并数列 不如直接套用其他Sort来加速
看来这样想法有错 感谢感谢
※ 编辑: KAINTS (122.116.222.216 台湾), 04/05/2021 09:01:17
15F：推 LPH66: 那正好会适得其反; 合并步骤只有线性才能 180.177.0.237 04/05 16:21
16F：→ LPH66: 得到整个演算法是 O(n log n) 180.177.0.237 04/05 16:21
17F：→ LPH66: 如果你的合并步骤是 O(n log n) 180.177.0.237 04/05 16:22
18F：→ LPH66: 则整个演算法会变成 O(n (log n)^2) 180.177.0.237 04/05 16:22
19F：→ LPH66: 反而稍微地变慢了 180.177.0.237 04/05 16:22