【算法图解】选择排序

算法表现

选择排序是基础排序算法，运行时间较长，具体算法表现如下：

1. 遍历整个数组，找出最大（最小）值，弹出原数组并将其放入新数组中。
2. 遍历剩余元素，找出最大（最小）值，弹出原数组并放入新数组中前一个数之后。
3. 重复第二步，得到新数组，排序完成。

代码表现

def findSmallest(arr):
    Smallest = arr[0]
    Smallest_index = 0
    for i in range(1,len(arr)):
        if arr[i] < Smallest:
            Smallest = arr[i]
            Smallest_index = i
    return Smallest_index
def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr)
        newArr.append(arr.pop(smallest))#append()给新数组添加元素，pop()将该元素弹出原数组
    return newArr

print selectionSort([5,3,6,2,10])

算法运行时间

第一次需要检查n个元素，随后依次是n-1，n-2，···，2和1。因此运行时间为O(n*1/2*n)，但是大O表示法常常省略1/2这样的常数，所以选择排序的算法运行时间为O(n^2).