我应该如何分析和或证明这个简单的排序算法？

Question

def modSwapSort(L): 
    """ L is a list on integers """
    print "Original L: ", L
    for i in range(len(L)):
        for j in range(len(L)):
            if L[j] < L[i]:
                # the next line is a short 
                # form for swap L[i] and L[j]
                L[j], L[i] = L[i], L[j] 
                print L
    print "Final L: ", L

Answer 1

它是某种形式的选择排序。其复杂度为O(n^2)。在for范围内进行一些简单的优化可能会有所帮助。因为现在在每一个i-循环步骤中，它在j-循环中创建最小的元素，并将其放在第i个位置，第二个最小的元素将在position(i-1)中，以此类推。因此，在每一个步骤中，您的列表看起来像(i=3):

[A1,A2,A3,B1,B2]其中Ak

So shorty：在每一个ith步骤中，您查找索引大于i的最少元素，该元素将大于列表中的第一个元素。