选择排序与python实现

1.算法思想

n 个元素，假设前 i 个元素已经排好序，从i+1到n个元素中选出最小的元素放在它在有序表中的最终位置上

2.代码实现

（1）非递归调用

def SelectionSort(A, n):
    for i in range(0, n-2):
        mini = i
        for j in range(i+1, n):
            if A[j] < A[mini]:
                i = j
        A[i],A[mini] = A[mini], A[i]  #swap
        print A


if __name__=='__main__':
    A = [6,5,4,3,2,1]
    SelectionSort(A, len(A))
    print A

（2）递归调用

def SelectionSort(a, k, n):
    if(k == n): return
    mini = k
    for j in range(k, n):
        if a[j] < a[mini]:
            mini = j
            a[k],a[mini] = a[mini], a[k] #swap
            print a
    SelectionSort(a, k+1, n)

if __name__=='__main__':
    a = [6,5,4,3,2,1]
    SelectionSort(a, 0, len(a))
    print a

3. 时间复杂度

对于任何输入来说，选择排序都是一个O(n^2)的算法。