数据结构|冒泡排序与选择排序

欢迎点击「算法与编程之美」↑关注我们!

本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。

冒泡排序

排序算法可以说是算法中使用的比较频繁的,冒泡排序是一种简单的排序,它通过遍历,一次比较两个元素,如果排序错误就交换位置,遍历需要重复进行直到不再需要交换,才算排序完成。

冒泡排序的思路如下:

1.比较相邻的元素,如果前一个比后一个大(升序,降序则相反),就交换这两个元素的位置。

2.对每一对相邻元素做同样的工作,从开始第一对到结尾最后一对。这步做完后,最后的元素会是最大的数。

3.针对所有的元素重复重复以上的步骤,除了最后一个。

4持续每次对越来越少的元素重复上面的操作,直到没有任何一对数字需要比较。

冒泡排序图示

53

22

87

12

65

47

55

20

22

53

87

12

65

47

55

20

22

53

87

12

65

47

55

20

22

53

12

87

65

47

55

20

22

53

12

65

87

47

55

20

22

53

12

65

47

87

55

20

22

53

12

65

47

55

87

20

22

53

12

65

47

55

20

87

时间复杂度:O(n^2)

代码实现

冒泡排序的代码实现并不难,对于初学者来说只需要注意循环次数这个坑就行。不难发现,冒泡排序的代码实现需要两层循环才能实现。

第一层(内层循环):每次将相邻的两个元素进行对比,使最大值移动到列表尾部

第二层(外层循环):第一层循环,第一次执行只能保证最后一位的元素位置正确,第二次保证倒数第二位的位置正确,以此类推,需要执行N-1次第一层循环,这就需要一个外层循环来实现。

以上述图片为例,共8个元素

第一次排序,两两对比,共对比7次

第二次排序,两两对比,共对比6次

。。。。。。

随着元素个数的变化,外层循环和内存循环的次数都在变化,我们就需要将外层循环和内存循环的循环次数联系在一起。

外层循环执行次数

外层循环

内层循环

第一次

J=0

需要执行n-1次

第二次

J=1

需要执行n-1-1次

第三次

J=2

需要执行n-1-2次

。。。。。。

选择排序

时间复杂度:O(n^2),虽然选择排序和冒泡排序的时间复杂度一样,但实际上,选择排序进行的交换操作很少,最多会发生 N - 1次交换。而冒泡排序最坏的情况下要发生N^2 /2交换操作。从这个意义上讲,交换排序的性能略优于冒泡排序。而且,交换排序比冒泡排序的思想更加直观。

选择排序思路

将本次遍历的第一个元素视为最小值,用mixValue记录其下标,遍历一次列表,只要存在比最小值小的数,便将当前下标赋值mixValue。本次遍历结束便交换最小值和遍历起始位的数。重复上述操作,每次遍历便将遍历起始位往后移一位,这样便能让数值小的数不断往前移。

更多精彩文章:

算法|从阶乘计算看递归算法

算法|字符串匹配(查找)-KMP算法

JavaScript|脚本岂能随意放置

开发|优秀的Java工程师的“对象”一定不错

谈一谈|2019蓝桥杯回顾与分享

where2go 团队


微信号:算法与编程之美

温馨提示:点击页面右下角“写留言”发表评论,期待您的参与!期待您的转发!

本文分享自微信公众号 - 算法与编程之美(algo_coding)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券