【从 0 到 1 学算法】6.Select Sort 算法
选择排序是什么?
选择排序是基础排序的一种,它的思路是,原数列分为有序和无序部分,每次从无序部分中 挑出极值放入有序数列部分
算法原理
对于数列{5,3,7,2,1,9,8,4}进行从小到大选择排序初始 有序部分为空 无序部分为 5 3 7 2 1 9 8 4
第一趟:1 3 7 2 5 9 8 4,有序部分为 1 无序部分为 3 7 2 5 9 8 4,元素 1 的位置与元素 5 的位置对换
第二趟:1 2 7 3 5 9 8 4 ,有序部分为 1 2 无序部分为 7 3 5 9 8 4 ,元素 2 的位置与元素 3 的位置对换
第三趟:1 2 3 7 5 9 8 4,有序部分为 1 2 3 无序部分为 7 5 9 8 4,元素 3 的位置与元素 5 的位置对换
第四趟:1 2 3 4 5 9 8 7 ,有序部分为 1 2 3 4 无序部分为 5 9 8 7 ,元素 4 的位置与元素 7 的位置对换
第五趟:1 2 3 4 5 9 8 7,有序部分为 1 2 3 4 5 无序部分为 7 9 8,元素 5 的位置与元素 5 的位置对换
第六躺:1 2 3 4 5 7 8 9,有序部分为 1 2 3 4 5 7 无序部分为 8 9,元素 7 的位置与元素 9 的位置对换
第七趟:1 2 3 4 5 7 8 9,有序部分为 1 2 3 4 5 7 8 无序部分为 9,元素 8 的位置与元素 8 的位置对换,但因为现在只有一个元素无序 所以其实以及排序完了
可以看出几个问题
1.可以看出 8 个元素排序 7 趟
2.选择排序是选择无序部分的第一个元素与剩下元素的极值进行交换,最后吧无序部分的第一个元素加入有序部分
3.可以看出第五趟与第七趟都进行 与自身的交换,这里是优化点
代码示例
结果:
第 1 趟
1 3 7 2 5 9 8 4
第 2 趟
1 2 7 3 5 9 8 4
第 3 趟
1 2 3 7 5 9 8 4
第 4 趟
1 2 3 4 5 9 8 7
第 6 趟
1 2 3 4 5 7 8 9
可以看出优化后少了第五趟与第七趟的的交换
选择排序和冒泡排序的异同
相同点:
1.它俩都是基础排序 时间复杂度都是 O(n 2 n^2n )
2.它俩都是基于交换来进行排序
不同点:
1.选择排序是不稳定排序 1,冒泡排序是稳定排序
2.选择排序在顺序度乱的情况下时间复杂度优于冒泡排序,因为选择排序每一趟只是记录下标值最终只是交换了一次,而冒泡排序每趟需要交换很多次。
3.优化后的冒泡排序在顺序度顺的情况下时间复杂度优于选择排序,因为优化后的冒泡排序 趟数与交换的次数会大幅度减少,但选择排序则不行
额外补充
不稳定排序是指,排序后元素的相对前后位置发生了变化,例如 5 8 5 2 9,选择排序后是 2 5 5 8 9,但此时的 5 5 与原数列的相对前后位置是发生变化的。而冒泡排序是不变的,所以冒泡排序是稳定排序。
版权声明: 本文为 InfoQ 作者【Geek_65222d】的原创文章。
原文链接:【http://xie.infoq.cn/article/b61c768e537dd7c30e4693af1】。未经作者许可,禁止转载。
评论