第三章 - Python 内置数据结构
简单选择排序
简单选择排序
- 属于选择排序
- 两两比较大小,找出极值(极大值或极小值)被放置在固定的位置,这个固定位置一般指的是某一端
- 结果分为升序和降序排列
降序
- n个数从左至右,索引从0开始到n-1,两两依次比较,记录大值索引,此轮所有数比较完毕,将大数和索引0数交换,如果大数就是索引1,不交换。第二轮,从1开始比较,找到最大值,将它和索引1位置交换,如果它就在索引1位置则不交换。依次类推,每次左边都会固定下一个大数。
- 升序
- 和降序相反
简单选择排序
简单选择排序代码实现(一)*
1 | m_list = [ |
简单选择排序代码实现(二)
- 优化实现
二元选择排序
同时固定左边最大值和右边最小值
优点:
减少迭代元素的次数
1、length//2 整除,通过几次运算就可以发现规律
2、由于使用了负索引,所以条件中要增加
i == length + minindex
还有没有优化的可能?
1 | count_swap = 0 |
简单选择排序代码实现(二)
- 改进实现
如果一轮比较后,极大值、极小值的值相等,说明比较的序列元素全部相等
1 | m_list = [ |
简单选择排序代码实现(二)
- 改进实现
[1, 1, 1, 1, 1, 1, 1, 1, 2] 这种情况,找到的最小值索引是-2,最大值索引8,上面的代码会交换2次,最小值两个1交换是无用功,所以,增加一个判断
1 | m_list = [ |
简单选择排序总结
- 简单选择排序需要数据一轮轮比较,并在每一轮中发现极值
- 没有办法知道当前轮是否已经达到排序要求,但是可以知道极值是否在目标索引位置上
- 遍历次数1,…,n-1之和n(n-1)/2
- 时间复杂度O(n2)
- 减少了交换次数,提高了效率,性能略好于冒泡法