数据结构（八）python实现选择排序

数据结构（八）python实现选择排序

原理：

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的后面。依此类推，直到所有元素均排序完毕。

首先找到数组中最小的那个元素,其次,将它和第一个元素交换。接下来找第二小和第二个交换......

如图：

python实现：

# 选择排序（升序）
def select_sort(li):n = len(li)# j代表当前有序的序列长度for j in range(0,n-1):# 1 遍历比较，默认第0个元素是最小min_index = j# 从第0个元素之后（j+1），遍历比较，拿到最小值元素li[i]for i in range(j + 1, n):if li[i] < li[min_index]:# 至此min_index就是最小值元素的索引min_index = i# 2 交换最小值和无序序列首个元素(即把最小值元素放到第0个位置:li[j])li[j], li[min_index] = li[min_index], li[j]# 3 对剩余无序序列(li[1:n])重复步骤1 2if __name__ == '__main__':li = [6, 3, 1, 9, 2, 5, 8, 7, 4]select_sort(li)print(li)

应用场景：

当n较小时(n≤50)，采用选择排序

时间复杂度：

时间复杂度：O(n^2)
稳定性：不稳定