我正在编写用于合并排序的代码(Haskell)。
我对根据顺序将两个列表放在一起的函数有疑问。
(即[1,4,7] [2,5,6]-> [1,2,4,5,6,7])
这是我的原始代码。 (xs，ys是参数，zs是累加器。)
msort4 [] ys zs = zs ++ ys
msort4 xs [] zs = zs ++ xs
msort4 allx@(x:xs) ally@(y:ys) zs
| x <= y = msort4 xs ally (zs ++ [x])
| otherwise = msort4 allx ys (zs ++ [y])
这是我在引用网上找到的代码后编写的第二个代码。
msort4 [] ys = ys
msort4 xs [] = xs
msort4 allx@(x:xs) ally@(y:ys)
| x <= y = x :msort4 xs ally
| otherwise = y : msort4 allx ys
仅有这么小的差异，我的代码有了很大的改进。
我正在排序大约500个单词的列表，而我的原始代码大约需要2.5秒，而新的代码平均需要0.4秒。
我想知道为什么我的速度这么慢，而在线的速度却快得多，即使它们看起来很相似。 (我什至以为我会更快，因为我不需要来回走动。)
提前致谢。
最佳答案
(:)到列表的前面是O(1)，(++)是O(n)其中n是左列表的长度
随着zs变大，您每次必须遍历整个列表，只是添加一个元素[x]