数字的比较，使用合并排序

Question

如果你有5个不同的号码,如何许多的比较至多做你需要理清这种使用合并排序？

Answer 1

我觉得这个问题有意思，所以我决定深入探索它（与Python中的小实验）。

我下载从此处 mergesort.py和修改它添加cmp参数为一个比较器功能。然后：

import collections
import itertools
import mergesort
import sys

class CountingComparator(object):
  def __init__(self):
    self.count = 0
  def __call__(self, a, b):
    self.count += 1
    return cmp(a, b)

ms_histo = collections.defaultdict(int)

for perm in itertools.permutations(range(int(sys.argv[1]))):
  cc = CountingComparator()
  lperm = list(perm)
  mergesort.mergesort(lperm, cmp=cc)
  ms_histo[cc.count] += 1

for c in sorted(ms_histo):
  print "%d %2d" % (c, ms_histo[c])

将所得的简单直方图（从长度为4，因为我为开发和调试这个）是：

4  8
5 16

有关张贴，用5代替4的长度的问题，我得到：

5  4
6 20
7 48
8 48

和具有6的长度（和更宽的格式; - ）：

7    8
8   56
9  176
10 288
11 192

最后，7的长度（和更广泛的格式; - ）：

 9   16
10  128
11  480
12 1216
13 1920
14 1280

当然一些完美的规则组合公式潜伏在这里，但我发现很难衡量它可能是什么，无论是分析还是通过钻研的数字。任何人的建议了？

Answer 2

什么是从编码合并排序，保持一个计数器在它的比较次数阻止你，并尝试出来的[0,1,2,3,4]的所有排列？

Answer 3

当合并排序的两个名单的长度L1和L2，我想最糟糕的是数量比较是L1+L2-1.

• 最初有五个1-长名单。
• 你可以合并两个对名单 2比较, ，造成在清单的长度的2，2，1.
• 然后你就可以合并2和1个长长的清单与在大多数另有1+2-1= 2比较, 产生2和3的长长的名单。
• 最后合并这些清单在最2+3-1= 4比较.

所以我猜答案是8。

这个序列的数字，结果在上述：[2], [4], [1], [3], [5] -> [2,4], [1,3], [5] -> [2,4], [1,3,5] -> [1,2,3,4,5]

编辑：

这里是一个天真的爱尔兰实施。在此基础上，数的比较是5、6、7或8对于排列的1..5.

-module(mergesort).

-compile(export_all).


test() ->
  lists:sort([{sort(L),L} || L <- permutations()]).

sort([]) -> {0, []};
sort([_] = L) -> {0, L};
sort(L) -> 
  {L1, L2} = lists:split(length(L) div 2, L),
  {C1, SL1} = sort(L1), {C2, SL2} = sort(L2),
  {C3, RL} = merge(SL1, SL2, [], 0),
  {C1+C2+C3, RL}.

merge([], L2, Merged, Comps) -> {Comps, Merged ++ L2};
merge(L1, [], Merged, Comps) -> {Comps, Merged ++ L1};
merge([H1|T1], [H2|_] = L2, Merged, Comps) when H1 < H2 -> merge(T1, L2, Merged ++[H1], Comps + 1);
merge(L1, [H2|T2], Merged, Comps) -> merge(L1, T2, Merged ++[H2], Comps + 1).


permutations() ->
  L = lists:seq(1,5),
  [[A,B,C,D,E] || A <- L, B <- L, C <- L, D <- L, E <- L, A =/= B, A =/= C, A =/= D, A =/= E, B =/= C, B =/= D, B =/= E, C =/= D, C =/= E, D =/= E].

Answer 4

http://www.sorting-algorithms.com/

Answer 5

根据维基百科：在最坏的情况下，合并排序确实的量

- 比较等于或大于（2 ^⌈lgn⌉+ 1 N⌈lgn⌉）稍小的

Answer 6

有关刚好五个不同的数字进行排序，你可以比较的最大数量是8和比较的最低数量为7这里的原因： -

假设该阵列是A，B，C，d，E

分递归：A，B，c和d，E

分递归：A，B和c和d＆E

分递归：a和b＆c和d＆E

现在，合并这将需要比较 -

A＆B：一个比较，以形成A，B

A，B和C：两个比较，以形成A，B，C

d＆E：一个比较，以形成d，E

A，B，c和d，E：4个比较在最坏的情况下或三个比较ID d是阵列的最大元素，以形成，B，C，d，E

所以，比较的总数将是最坏的情况下8和7中最好的情况下。