Python中怎么实现选择排序

这篇文章给大家介绍Python中怎么实现选择排序，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。

选择排序（Selection Sort）

选择排序（Selection Sort）是基于冒泡排序做的改进，保留了了冒泡排序中的多趟比较，每一趟依然都会将最大项移动到最末尾。不同点在于，冒泡排序不论是否需要交换，都会将每个相邻元素进行比对，但选择排序是记录下最大值的索引，在遍历完当前趟的列表后，将最大值与最后一项元素交换。

• 选择排序的比对次数时间复杂度：O(n^2)
  

• 选择排序的交换次数时间复杂度：O(n)

冒泡排序：Python数据结构与算法——冒泡排序

选择排序关键：记录最大项位置

 

算法思路：

1. 第一趟选择排序：n-1次比对，记录最大项位置，与最后一项元素交换

2. 第二趟选择排序：n-1个元素，n-2次比对，记录最大项位置，与当前这趟最后一项元素交换

3. 第三趟选择排序：n-2个元素，n-3次比对，记录最大项位置，与当前这趟最后一项元素交换

……

n-1. 第n-1趟选择排序：2个元素直接比对

关于Python中怎么实现选择排序就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。