算法 - 雙端選擇排序真的比單端排序更快嗎？

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）