选择排序（Selection sort）是一种简单直观的排序算法。

原理

是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序的交换操作介于 0 和 (n - 1） 次之间，所以选择排序是不稳定的排序方法。

算法描述

1. 在一个长度为 n 的无序数组中，第一次遍历 n-1 个数找到最小的和第一个数交换。
2. 第二次从下一个数开始遍历 n-2 个数，找到最小的数和第二个数交换。

3. 重复以上操作直到第 n-1 次遍历最小的数和第 n-1 个数交换，排序完成。

   时间复杂度

   需要的总时间为O(n×n)，即O(n²)。

python语言实现

# -*- coding: UTF-8 -*-
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))
  return newArr

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

# 输出结果 [2, 3, 5, 6, 10]

当然，还有更简洁的实现方法：

# -*- coding:utf-8 -*-
# 选择排序

# 方法一
def select_sort(list):
    l = len(list)
    if l < 2:
        return list
    
    for i in range(l):
        min = list[i]
        for j in range(i + 1, l):
            if list[j] < min:
                min, list[j] = list[j], min
        list[i] = min

    return list


# 方法二，交换次数少，效率更高
def select(list):
    l = len(list)
    if l < 2:
        return list
    
    for i in range(l):
        for j in range(i + 1, l):
            if list[j] < list[i]:
                list[i], list[j] = list[j], list[i]

    return list


list = [54, 26, 93, 17, 77, 3, 31, 44, 55, 20]
print(select(list))
print(select_sort(list))