Python排序算法——选择排序
有趣的事,Python永远不会缺席!
如需转发,请注明出处:小婷儿的python https://www.cnblogs.com/xxtalhr/p/10787340.html
一、选择排序(Selection sort)
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,所以称为:选择排序。
1、原理
- 设第一个元素为比较元素,依次和后面的元素比较,比较完所有元素找到最小的元素,将它和第一个元素互换
- 重复上述操作,我们找出第二小的元素和第二个位置的元素互换,以此类推找出剩余最小元素将它换到前面,即完成排序
2、举例
举个例子,假设我现在有一个数列需要使用冒泡来排序 [11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22],
我们来看看使用冒泡的详细步骤:
1、首先11作为比较元素和列表后面的所有元素比较,找到最小的11,并放在第一位,第一轮完了,列表
是 [11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]
2、然后,99作为比较元素,和后面的元素[33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]作比较,找到最小的11,
和第二位元素99交换位置,即第二轮比较完后,列表为 [11, 11, 33 , 69, 77, 88, 55, 99, 33, 36,39, 66, 44, 22]
3、第三轮比较完,22最小,和第三个元素33交换位置,列表变为 [11, 11, 22, 69, 77, 88, 55, 99, 33, 36,39, 66, 44, 33]
4、最终得到列表 [11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]
注:是一轮比较完后,找出最小的,再交换这个元素和对应轮数位置处的元素位置,每轮只交换一次。二冒泡排序是,没比较一次,就交换一次位置,每轮要交换很多次。
二、代码
代码用jupyternotebook实现
实现思路: 使用双重for循环,内层变量为i, 外层为j,在内层循环中不断的比较相邻的两个值(j, j+1)的大小,如果j+1的值大于j的值,交换两者位置,每循环一次,外层的i增加1,等到i等于(len(arr) - 1)的时候,结束循环
第一次看不懂很正常,不要灰心,下面是 jupyter 使用代码的实现
def selection_sort(arr):
"""选择排序"""
# 第一层for表示循环选择的遍数
for i in range(len(arr) - 1):
# 将起始元素设为最小元素
min_index = i
# 第二层for表示最小元素和后面的元素逐个比较
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_index]:
# 如果当前元素比最小元素小,则把当前元素角标记为最小元素角标
min_index = j
# 查找一遍后将最小元素与起始元素互换
arr[min_index], arr[i] = arr[i], arr[min_index]
return arr selection_sort([11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22])
#返回结果 [11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]
三、特点
选择排序和冒泡排序很类似,但是选择排序每轮比较只会有一次交换,而冒泡排序会有多次交换,交换次数比冒泡排序少,就减少cpu的消耗,所以在数据量小的时候可以用选择排序,实际适用的场合非常少。
比较性:因为排序时元素之间需要比较,所以是比较排序
稳定性:因为存在任意位置的两个元素交换,比如[5, 8, 5, 2],第一个5会和2交换位置,所以改变了两个5原来的相对顺序,所以为不稳定排序。
时间复杂度:我们看到选择排序同样是双层循环n*(n-1)),所以时间复杂度也为:O(n^2)
空间复杂度:只需要常数个辅助单元,所以空间复杂度也为O(1)
记忆方法:选择对象要先选最小的,因为嫩,哈哈
结果
Successfully !!!
有趣的事,Python永远不会缺席!还不来加我,瞅什么瞅。
最新文章
- sql server 里类似replace的字符串子串删除
- Linux LVM硬盘管理之一:概念介绍
- JSF页面中使用js函数回调后台bean方法并获取返回值的方法
- SQL获取时间段内的所有月份
- Distinct和Group by去除重复字段记录
- WINDOWS下的SALT-MINION安装流水图
- ThinkPHP自动验证
- 40. Testing Prev 	Part IV. Spring Boot features
- 操作PDF文档功能的相关开源项目探索——iTextSharp 和PDFBox
- 通过demo搞懂encode_utf8和decode_utf8
- leetcode先刷_Climbing Stairs
- testbench中将外部数据引入输出的方法(转载)
- ListView的局部刷新
- asp.net(C#)html无限分类树 可新增 删除 修改
- <;tangmuchw>;之新手vue项目小记--新建.vue文件,运行项目,出现error:This dependency was not found...
- 41. 包含min函数的栈
- 如何在Axure中使用FontAwesome字体图标
- 【机器学习】随机森林(Random Forest)
- JQ 给textarea赋值
- gcc 与 g++的区分较
热门文章
- 生理周期POJ 1006
- 2018-11-27 中文代码示例之Programming in Scala笔记第七八章
- java程序存入数据库中文乱码解决方案
- codeforces 632C The Smallest String Concatenation
- jQuery 实现文字不停闪烁效果
- UnrealEd3视图导航及常用快捷键
- Flume 1.7.0单机版安装
- [20190320]测试相同语句遇到导致cursor pin S的情况.txt
- 图文并茂 RAID 技术全解 – RAID0、RAID1、RAID5、RAID10
- ubuntu 安装FoxitReader福昕阅读器(转载)