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

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)