算法-双端选择排序真的比单端选择快吗？ [英] Algorithms - are double ended selection sorts really faster than single ended ones?

问题描述

一个双端选择排序（同时交换最小值和最大值）被认为是普通选择排序的更快，即使比较的次数相同。我了解它消除了某些循环，但是如果比较次数保持不变，它们将如何更快？

A double ended selection sort, one that swaps both min and max, is claimed to be faster to be an ordinary selection sort, even thought the number of comparisons is the same. I understand that it gets rid of some of the looping, but if the number of comparisons stay the same, how are they faster?

预先感谢

推荐答案

这里是对选择排序和双端选择排序进行计数比较的实现。

Here's implementations of selection sort and double ended selection sort that count comparisons performed.

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

If you run it, you'll see that double-ended selection sort always performs more comparisons than regular selection sort.

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

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

That's because the number of comparisons for regular selection sort is:

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

对于双端选择排序，比较次数为（对于奇数n-偶数情况相似）

For double-ended selection sort, the number of comparisons is (for odd n -- the even case is similar)

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（ni）重写为（ni）+（ni-1）+ 1 ）

(Here, I'm rewriting each term 2(n-i) as (n-i) + (n-i-1) + 1)

这篇关于算法-双端选择排序真的比单端选择快吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！