python实现选择排序算法-阿里云开发者社区

开发者社区> python之战> 正文

python实现选择排序算法

简介: 选择排序,简单而直观,其原理是把序列中的最小值或者最大值找出来放在起始位置,然后再从剩下的序列中找出极值放到起始位置之后,以此类推最后就完成排序。 完成这个过程大致思想:首先需要一个记录器,记录排序排到第几个位置了,然后在剩余的序列中找到极值下标,最后将记录器位置和极值位置元素交换,完成本次选择排序。
+关注继续查看

选择排序,简单而直观,其原理是把序列中的最小值或者最大值找出来放在起始位置,然后再从剩下的序列中找出极值放到起始位置之后,以此类推最后就完成排序。

完成这个过程大致思想:首先需要一个记录器,记录排序排到第几个位置了,然后在剩余的序列中找到极值下标,最后将记录器位置和极值位置元素交换,完成本次选择排序。

用python实现比较简单:

def select_sort(items):
    n 
= len(items)
    for cur in range(n-1):
       item_max 
cur
       for i in range(cur+1, n):
           if items[i] > items[item_max]:
               items[i], items[item_max] 
= items[item_max], items[i]
       if item_max != cur:
           items[cur], items[item_max] = items[item_max], items[cur]


2019-04-15-23_08_10.png

关于选择排序的时间复杂度:

选择排序的交换操作介于 0 和 (n - 1) 次之间。选择排序的比较操作为 n (n - 1) / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1) 次之间。


比较次数O(n^2),比较次数与关键字的初始状态无关,总的比较次数N=(n-1)+(n-2)+...+1=n*(n-1)/2。交换次数O(n),最好情况是,已经有序,交换0次;最坏情况交换n-1次,逆序交换n/2次。交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CPU时间多,n值较小时,选择排序比冒泡排序快。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
JavaScript ~ 排序算法(选择排序)
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Title</title> <link type="text/css" rel="stylesheet" href="style/flex.
943 0
小记 用python进行排序
Linux 中可以使用 sort 进行排序,python中也一样,那么怎样实现把一个数字的 list 从小到大排序,然后写入文件,然后从文件中读取出来文件内容,然后反序,再追加到文件的下一行中呢? 思路如下: 1、取一个列表内容 2、对列表内容使用 sort 进行排序,并打...
767 0
python实现希尔排序算法
希尔排序是插入排序的一种又称“缩小增量排序”,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
1146 0
【算法导论】选择排序法
选择排序法         选择排序其实是冒泡法的一种改进,其基本思路也是:先确定最小元素,再找次最小元素,最后确定最大元素。         它与冒泡排序的最大区别在于:冒泡排序是只要碰见比它大的元素就交换,而选择排序是直接将元素放在最终的确定位置,从而避免了多次交换过程。
932 0
python实现插入排序算法
插入排序,其原理是通过构建一个初始的有序序列,然后从无需序列中抽取元素,插入到有序序列的相对排序位置,就像将一堆编号混乱的书,一本一本的放到书架上,找到上下编号之间的位置插入,最后完成整理。 python实现插入排序并不难,从第二个位置开始遍历,与它前面的元素相比较,如果比前面元素小就交换位置,实...
832 0
【大创_社区划分】——PageRank算法的解析与Python实现
一、什么是pagerank PageRank的Page可是认为是网页,表示网页排名,也可以认为是Larry Page(google 产品经理),因为他是这个算法的发明者之一,还是google CEO(^_^)。
1100 0
ML/DL:关于机器学习、深度学习算法模型的选择
ML/DL:关于机器学习、深度学习算法模型的选择
32 0
+关注
python之战
专注python学习与应用擅长爬虫、web、全栈,专注RPA技术实施;(个人公号:Python之战)
90
文章
0
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载