数据结构|冒泡排序与选择排序
欢迎点击「算法与编程之美」↑关注我们!
本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。
冒泡排序
排序算法可以说是算法中使用的比较频繁的,冒泡排序是一种简单的排序,它通过遍历,一次比较两个元素,如果排序错误就交换位置,遍历需要重复进行直到不再需要交换,才算排序完成。
冒泡排序的思路如下:
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。本次遍历结束便交换最小值和遍历起始位的数。重复上述操作,每次遍历便将遍历起始位往后移一位,这样便能让数值小的数不断往前移。
更多精彩文章:
where2go 团队
微信号:算法与编程之美
长按识别二维码关注我们!
温馨提示:点击页面右下角“写留言”发表评论,期待您的参与!期待您的转发!