简单选择排序

简单选择排序属于选择排序。

算法原理

基本思想是，第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]进行交换；第二次从arr[1]~arr[n-1]中选取最小值，与arr[1]进行交换，以此类推，第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]进行交换，总共通过n-1次，得到一个顺序排列的数组。

import random
import time

def selection_sort(array):
    for i in range(len(array)-1):
        min_index = i
        for j in range(i+1, len(array)):
            if array[j] < array[min_index]:
                min_index=j
        array[i], array[min_index] = array[min_index],array[i]

#生成10000个值在0~10000的随机数
myList=[random.random()*10000 for i in range(10000)]
start_time = time.time()
selection_sort(myList)
print(myList)
print(f"Time taken: {time.time() - start_time}")

复杂度分析

比较的次数为N(N-1)/2，移动的次数与数组的初始排序有关，当序列是正序时，移动次数最少，为0；当序列反序时，需要移动3N次。所以最坏时间复杂度为O(N^2)，最好时间复杂度和平均时间复杂度也是O(N^2)，因为没有引入其它的空间，空间复杂度是O(1)。

它是不稳定的排序算法，每一轮都会选择最后排序位置的最小元素，相等的元素在排序过程中会发生位置交换。