11.5.1 排序算法简介
所谓排序,是指将数据集合中的元素按从小到大的顺序进行排列,或按从大到小的顺序进行排列。前者称为升序排序,后者称为降序排序。在数据结构与算法这门课程中,我们会学习到诸多与排序相关的算法,比如冒泡排序算法,选择排序算法,快速排序算法,堆排序算法等。在本节教程中,我们来掌握非常经典的选择排序算法。
11.5.2 选择排序算法
选择排序的核心思想: 从数据集合中选出最小(大)的一个元素,存放在区间的起始位置,再从剩余的未排序元素中寻找到最小(大)的元素,放到已排序的区间的末尾,不断重复这样的过程,直至实现排序。下图所示为将最小值1选择到区间首部的过程:
(1) 初始情况下假定最小值为3,最小值索引为0
(2) 将元素3与元素2进行比较,2比3小,更新最小值索引为元素2的索引1
(3) 将索引1对应的元素2与末尾的1进行比较,1比2小,更新最小值索引为元素1的索引2
(4) 最小值索引2不等于初始的最小值索引0,故将元素3与1进行互换。
根据以上原理,我们现在使用Python语言来实现选择排序算法:
""" @author: 薯条老师 @desc: 实现选择排序算法 """ numbers = [3, 2, 1] n = len(numbers) # n个元素需要选择n-1趟才能实现排序,所以是n-1 for outer_index in range(n-1): # 先假定outer_index索引指向的元素为最小值 min_index = outer_index # 每次用当前元素与剩下的所有元素进行比较,所以是[outer_index+1, n) for inner_index in range(outer_index+1, n): if numbers[inner_index] < numbers[min_index]: # 在比较的过程中,一旦发现元素值比min_index指向的元素还小,就更新索引 min_index = inner_index # 循环结束后判断min_index是否等于一开始赋值的outer_index if min_index != outer_index: """ 如果min_index非等于outer_index, 就说明剩余的元素中有比一开始假定的最小值还小 此时,就应该互换位置。此即选择排序的核心,选择一个最大的或最小的,然后互换位置 """ numbers[outer_index], numbers[min_index] = \ numbers[min_index], numbers[outer_index] print(numbers)
11.5.3 最具实力的小班培训
薯条老师在广州有开设线下培训班,小班授课模式,一班最多6个人。也可一对一授课,全程帮助你学好计算机,实现高薪就业。不在广州的同学可提供住宿,也可以报名线上小班,用腾讯会议上直播课。
(1) Python后端工程师高薪就业班,月薪11K-18K,免费领取课程大纲
(2) Python高级爬虫+安卓逆向工程师就业班,月薪15K-25K,包拿Offer
(3) Python数据分析+商业分析+数据科学就业班,企业级项目实战,月薪10K-20K
(4) Python量化交易就业班,A股+期货+数字货币量化,月薪10K-40K
(5) Python机器学习+深度学习算法工程师,月薪20-50K
跟薯条老师学习的学生有拿到花生日记,林氏家居,南方电网,中国邮政集团,京东, 阿里等公司的offer, 学生的最低薪资有6K,最高薪资有18K, 平均就业薪资有11000。
扫码咨询薯条老师: