排序5个元素具有最小元件相比(Sorting 5 elements with minimum ele

我不得不排序5个元素的列表，在Python，使用元素之间的比较的最小数目的执行计划建模。除此之外，复杂性是无关紧要的。

其结果是代表排序在其他时间列表中所需的比较对的列表。

我知道有，这是否在7个比较（元之间，总是不复杂明智）的算法，但我不能找到一个可读（对我来说）的版本。

我怎样才能在7个比较了5个元素进行排序，并建立排序的“执行计划”？

PD：不做作业。

Answer 1:

这符合您的排序说明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有称为可爱模块算法:: Networksort ，让您与这些玩。玻色-尼尔森算法由克努特为几个比较引用，你可以看到它在这里。

编辑

一个插入排序也是行之有效的：

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