python - 以最少的元素比较对 5 个元素进行排序

Question

我必须在 python 中使用元素之间的最小比较次数来对排序 5 个元素的列表的执行计划进行建模。除此之外，复杂性无关紧要。

结果是一个对列表，表示在另一个时间对列表进行排序所需的比较。

我知道有一种算法可以在 7 次比较中做到这一点（元素之间，总是，而不是复杂性），但我找不到可读的（对我来说）版本。

如何对 7 个比较中的 5 个元素进行排序，并为排序构建“执行计划”？

PD：不是作业。

Answer 1

好吧，有 5!=120 种方式可以对元素进行排序。每次比较都会为您提供一点信息，因此您至少需要进行 k 次比较，其中 2^k >= 120。您可以检查 2^7 = 128，因此 7 是您需要执行的最少比较次数。

Answer 2

这符合您对排序的描述5 elements in 7 comparisons：

import random

n=5
ran=[int(n*random.random()) for i in xrange(n)]
print ran

def selection_sort(li):  
    l=li[:]                  
    sl=[]        
    i=1         
    while len(l):              
        lowest=l[0]            
        for x in l:            
            if x<lowest:      
                lowest=x  
        sl.append(lowest)  
        l.remove(lowest)     
        print i  
        i+=1
    return sl

print selection_sort(ran)  

这使用不是最有效的选择排序，但确实使用很少的比较。

这可以缩短为：

def ss(li):  
    l=li[:]                  
    sl=[]                 
    while len(l):              
        sl.append(l.pop(l.index(min(l))))       
    return sl    

在任何一种情况下，都会打印如下内容：

[0, 2, 1, 1, 4]
1
2
3
4
5
[0, 1, 1, 2, 4]

Perl 有一个可爱的模块，叫做Algorithm::Networksort，它允许你玩这些。Knuth 为少数比较器引用了 Bose-Nelson 算法，您可以在此处查看。

编辑

插入排序也很有效：

def InsertionSort(l):
    """ sorts l in place using an insertion sort """
    for j in range(1, len(l)):
        key = l[j]
        i = j - 1
        while (i >=0) and (l[i] > key):
            l[i+1] = l[i]
            i = i - 1

        l[i+1] = key

Answer 3

我最终使用了带有自定义比较运算符的常规排序算法（插入排序），该运算符中断排序并逐步构建执行计划以恢复或重现该过程。

这很丑：该函数引发了一个异常，封装了继续排序所需的信息。然后可以使用新信息重试排序，可能会再次中止。

由于排序尝试发生在 http 请求的范围内，因此性能对我来说不是问题。