Python选择排序算法详解与实现

本文详细介绍Python中的选择排序算法，包含其定义、工作原理及具体用法示例，旨在为读者提供清晰的参考。

选择排序

选择排序的逻辑相对直观，可以类比为从一堆大小不一的球中挑选出最小的球（此处以从小到大排序为例，首先选出最小球）：

1. 选定一个基准球

2. 将基准球与其余所有球逐一比较，若发现比基准球更小的球，则交换它们的位置

3. 经过第一轮比较后，即可确定最小的球

4. 再次选择一个基准球，重复上述操作以找出次小的球

5. 持续执行步骤4，直至所有球排序完成

时间复杂度：O(n^2)。具体比较次数为第一轮 n-1 次，第二轮 n-2 次……最后一轮 1 次，总比较次数为 n*(n-1)/2。

以下是具体代码实现：

def selectedSort(myList):
  #获取list的长度
  length = len(myList)
  #一共进行多少轮比较
  for i in range(0,length-1):
    #默认设置最小值得index为当前值
    smallest = i
    #用当先最小index的值分别与后面的值进行比较,以便获取最小index
    for j in range(i+1,length):
      #如果找到比当前值小的index,则进行两值交换
      if myList[j]<myList[smallest]:
        tmp = myList[j]
        myList[j] = myList[smallest]
        myList[smallest]=tmp
    #打印每一轮比较好的列表
    print("Round ",i,": ",myList)
myList = [1,4,5,0,6]
print("Selected Sort: ")
selectedSort(myList)

执行结果如下：

此外，推荐一款排序算法的可视化工具供参考：

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具： http://tools.jb51.net/aideddesign/paixu_ys

感兴趣的朋友可以进一步查阅本站相关专题：《Python数据结构与算法教程》、《Python列表(list)操作技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》以及《Python入门与进阶经典教程》。

希望本文的内容能对大家的Python编程学习有所帮助。