选择排序

选择排序改进了冒泡排序，每次遍历列表只做一次交换。为了做到这一点，选择排序在遍历时寻找最大的值，并在完成遍历后，将其放置在正确的位置。遍历 n-1 次，排序 n 个项。以下展示了整个排序过程。

def selectionSort(alist):
    for fillslot in range(len(alist)-1,0,-1):
        positionOfMax=0
        for location in range(1,fillslot+1):
            if alist[location]>alist[positionOfMax]:
                positionOfMax = location
        temp = alist[fillslot]
        alist[fillslot] = alist[positionOfMax]
        alist[positionOfMax] = temp

你可能会看到选择排序与冒泡排序有相同数量的比较，因此也是 O(n2)。然而，由于交换数量的减少，选择排序通常在基准研究中执行得更快。事实上，对于我们的列表，冒泡排序有 20 次交换，而选择排序只有 8 次。