python排序算法——选择排序-创新互联
在尼泸西等地区,都构建了全面的区域性战略布局,加强发展的系统性、市场前瞻性、产品创新能力,以专注、极致的服务理念,为客户提供成都网站设计、做网站 网站设计制作按需设计,公司网站建设,企业网站建设,品牌网站建设,营销型网站建设,成都外贸网站制作,尼泸西网站建设费用合理。文章目录
- python排序算法——选择排序
- 一、前言
- 二、描述
- 三、代码实现
- 总结
一、前言
相关知识来自《python算法设计与分析》。初级排序算法是指几种较为基础且容易理解的排序算法。初级排序算法包括插入排序、选择排序和冒泡排序3种。虽然它们的效率相对于高级排序算法偏低,但是在了解初级排序算法之后,再去学习相对复杂的高级排序算法会容易许多。本文介绍选择排序。
二、描述选择排序表示从无序的数组中,每次选择最小或大的数据,从无序数组中放到有序数组的末尾,以达到排序的效果。
选择排序的平均时间复杂度是O(n2),最好情况下的时间复杂度和最坏情况下的时间复杂度都是O( n2 )。另外,它是一个不稳定的排序算法。选择排序的过程很容易理解。如图2-4所示,我们仍以递增排序的算法为例,先遍历未排序的数组,找到最小的元素。然后,把最小的元素从未排序的数组中删除,添加到有序数组的末尾。
因为最小的元素是1,所以1被添加到仍为空的有序数组末尾。
如图2-5所示,我们继续对剩余元素进行遍历。这次,最小的元素是2。我们把它添加到已排序的数组末尾。由于已在有序数组中的元素必定小于未排序数组中的所有元素,所以这步操作是正确无误的。
如图2-6所示,重复上述步骤,当未排序数组中只剩下一个元素时,把它添加到已排序的数组末尾,整个数组的排序就完成了。
选择排序代码:
nums = [5,3,6,4,1,2,8,7]
res = [] #用于存储已排序元素的数组
while len(nums): #当未排序数组内还有元素时,重复执行选择最小数的代码
minInd = 0 #初始化存储最小数下标的变量,默认为第一个数
for i in range(1, len(nums)):
if(nums[i]< nums[minInd]): #更新最小数的下标
minInd = i
temp = nums[minInd]
nums.pop(minInd) #把最小数从未排序数组中删除
res.append(temp) #把最小数插入到已排序数组的末尾
print(res)
运行程序,输出结果为:
[1,2,3,4,5,6,7,8]
在程序中,第一个for循环中的i代表了有序数组之后的第一个位置,也就是未排序数组中的第一个位置。随后,再使用一个for循环,在未排序数组中找到最小值的下标。首先,把最小值下标minInd初始化为未排序数组中第一个元素的下标。随后,遍历整个数组,遇到比目前的最小值更小的元素时,更新下标即可。找出最小值后,把它和未排序数组中的第一个元素交换位置,这时它就成了有序数组中的最后一个元素。
总结
以上就是要讲的内容,本文介绍了选择排序的理论知识和代码实现。选择排序表示从无序的数组中,每次选择最小或大的数据,从无序数组中放到有序数组的末尾,以达到排序的效果。选择排序的平均时间复杂度是O(n2),最好情况下的时间复杂度和最坏情况下的时间复杂度都是O( n2 )。另外,它是一个不稳定的排序算法。
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
当前题目:python排序算法——选择排序-创新互联
文章网址:http://scyanting.com/article/dhocgc.html