排序位置的简单实现

Question

在我的大学里，我的Python 101课程有以下的作业。

'''
Modify the naive implementation (see below) of a sorting algorithm so that
the list to be sorted is modified *in place*.

Here is the idea:

1. Iterate over all indices i = 0, 1, 2, ... of the input list

2. Find the index j of the smallest element in the rest of the list (from i on)

3. Replace the elements at indices i and j

If we want to sort the list [5, 3, 1, 4, 8, 2, 7, 6], for instance, a run of
the algorithm would be:

i=0, j=2, list=[5, 3, 1, 4, 8, 2, 7, 6]
i=1, j=5, list=[1, 3, 5, 4, 8, 2, 7, 6]
i=2, j=5, list=[1, 2, 5, 4, 8, 3, 7, 6]
i=3, j=3, list=[1, 2, 3, 4, 8, 5, 7, 6]
i=4, j=5, list=[1, 2, 3, 4, 8, 5, 7, 6]
i=5, j=7, list=[1, 2, 3, 4, 5, 8, 7, 6]
i=6, j=6, list=[1, 2, 3, 4, 5, 6, 7, 8]
'''

原则上，我唯一需要修改的两个函数是"index_of_smallest_element“和"naive_sort_inplace”。

def index_of_smallest_element(some_list):
    '''Returns the index of the smallest element in some_list'''
    guess=some_list[0]    
    for element in some_list:
        if element < guess:
            guess=element
    return some_list.index(guess)


def naive_sort(some_list):
    sorted_list = []
    while len(some_list) > 0:
        # remove smallest element from some_list
        smallest_element = some_list.pop(index_of_smallest_element(some_list))
        # ... and append it to sorted_list
        sorted_list.append(smallest_element)
    return sorted_list


def naive_sort_inplace(some_list):
    def exchange(some_list,x,y):
        some_list[x],some_list[y]=some_list[y],some_list[x]        


    for i in range(0,len(some_list)):        
        remaining_list=some_list[i:(len(some_list)+1)]
        i_rest=index_of_smallest_element(remaining_list)
        j=i+i_rest
        print('i=',i,'j=',j,'list=',some_list)
        exchange(some_list,i,j)
    return some_list


if __name__ == '__main__':
    my_list = [5, 3, 1, 4, 8, 2, 7, 6]
    naive_sort_inplace(my_list)
    print('Test: ', my_list == [1, 2, 3, 4, 5, 6, 7, 8])

虽然代码功能齐全，但我想知道是否会有更好的方法来实现它，特别是"naive_sort_inplace“函数。

Answer 1

问题

首先，当前的实现并不是真正到位的，因为切片操作创建了一个新的大小的列表，这违反了所需的最大常量额外空间使用。

此外，当您首先找到所需的值时，您将在index_of_smallest_element中执行双重工作，然后必须再次遍历整个列表以找到索引(索引调用具有线性时间成本)。

建议

在原地工作时，通常必须使用索引或指针，这种情况也是如此。大部分工作可以分为3类:索引工作、交换工作和控制流程，如果您正在做的工作超出了这些工作范围，那么您应该花更多的时间来考虑是否有问题的方向。

这意味着您应该手动跟踪相关的索引，在调用函数时，处理子集的方法是将描述这一点的索引传递给它。

溶液

有两个主要的改变要做，都连接到index_of_smallest_element。我们首先将该实现更改为：

def index_of_smallest_element(some_list, start=0):
    smallest = some_list[start]
    for i in range(start+1, len(some_list)):
       value = some_list[I]
       if value < smallest:
           smallest = value
           start = i
    return start

这样就可以很容易地编写朴素(而且非常糟糕)的就地排序：

def naive_sort_inplace(some_list, out=None):
    def exchange(some_list,x,y):
        some_list[x],some_list[y]=some_list[y],some_list[x]        


    for i in range(0,len(some_list)):
        j = index_of_smallest_element(remaining_list, i)
        if out is not None:
            out('i=',i,'j=',j,'list=',some_list)
        exchange(some_list,i,j)
    return some_list

我不太清楚你为什么要做所有的打印，但我认为这是为了测试或证明正确性。为了重用，我对其进行了更改，因此默认情况下它不会打印，但是如果传入print (或其他一些输出函数，如open(filename,'w').write)，则会将这些日志更新写入该输出函数。