The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list.

选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。时间复杂度为O(n^2)。

python实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 selection_sort(arr):      #对数组进行排序
        new_arr = []
        for i in range(len(arr)):
            smallest = findSmallest(arr)
            new_arr.append(arr.pop(smallest))
        return new_arr

参考书目：
[^1]: 《算法图解》【美】Aditya Bhargava. 编著