算法 - 双端选择排序真的比单端排序更快吗？

Question

双端选择排序，即交换最小和最大的排序，声称更快是一个普通的选择排序，即使认为比较的数量是相同的。我明白，它摆脱了一些循环，但如果比较的数量保持不变，它们如何更快？

在此先感谢

Answer 1

这里的选择排序和双端选择那种指望执行的比较的实现。

如果运行它，您会看到双端选择排序总是执行更多比常规选择排序。

import random 

def selsort(xs): 
    N = len(xs) 
    comparisons = 0 
    for i in xrange(N): 
     m = i 
     for j in xrange(i+1, N): 
      comparisons += 1 
      if xs[j] < xs[m]: m = j 
     xs[i], xs[m] = xs[m], xs[i] 
    return comparisons 

def deselsort(xs): 
    N = len(xs) 
    comparisons = 0 
    for i in xrange(N//2): 
     M = m = i 
     for j in xrange(i+1, N-i): 
      comparisons += 2 
      if xs[j] < xs[m]: m = j 
      if xs[j] >= xs[M]: M = j 
     xs[i], xs[m] = xs[m], xs[i] 
     if M == i: M = m 
     xs[N-i-1], xs[M] = xs[M], xs[N-i-1] 
    return comparisons 


for rr in xrange(1, 30): 
    xs = range(rr) 
    random.shuffle(xs) 
    xs0 = xs[:] 
    xs1 = xs[:] 
    print len(xs), selsort(xs0), deselsort(xs1) 
    assert xs0 == sorted(xs0), xs0 
    assert xs1 == sorted(xs1), xs1 

这是因为常规选择排序是比较的数量：

(n-1) + (n-2) + ... + 1 = n(n-1)/2 

对于双端选择排序，比较的数量是（奇数N - 偶的情况是相似的）

2(n-1) + 2(n-3) + 2(n-5) + ... + 2 
= (n-1)+(n-2)+1 + (n-3)+(n-4)+1 + ... 2+1+1 
= ((n-1) + (n-2) + ... + 1) + (n-1)/2 
= n(n-1)/2 + (n-1)/2 

（在这里，我重写每学期2(n-i)为(n-i) + (n-i-1) + 1）