选择排序的思路
选择排序改进了冒泡排序.将交换的次数由
O(N^2)
减少到O(N)
.但是比较的次数依然是O(N^2)
选择排序的思路
选定第一个索引位置,然后和后面元素依次比较
如果后面的队员,小于第一个索引位置的队员,则min = 当前位置,经过一轮后交换min和第一个索引的位置
经过一轮的比较后,可以确定第一个位置是最小的
然后使用同样的方法把剩下的元素逐个比较即可
可以看出选择排序,第一轮会宣传最小值,第二轮会选出第二个最小值,直到最后
(每一轮最多进行1次交换,一个遍历n-1次)
选择排序的效率
选择排序的比较次数
选择排序和冒泡排序的比较次数都是N*(N-1)/2
,也就是O(N^2)
选择排序的交换次数
选择排序每次进行选择的时候,最多需要交换1次,一共遍历多少次呢?N-1次
选择排序交换次数只有N-1
次,用大O表示法就是O(N)
所以选择排序通常认为在执行效率上是高于冒泡排序的