上节我们一起学习了简单插入排序，不过插入排序既然很慢，和冒泡排序真是患难兄弟了。但是插入排序也有一个好处就是所占空间很少，额外空间只有一个存储临时变量的空间就够了。
这节我们一起来学习一下简单选择排序算法。
简单选择排序的基本思想就是（以从小到大为例）：在要排序的一组数中，选出最小的一个数与第一个数交换，然后再在第二个数到最后一个数中找到最小的一个数与第二个数交换，以此类推，知道倒数第二个书与最后一个数比较为止。
这个比较好理解了。下面距离说明。
初始序列为3、1、5、7、2、4、9
第一趟排序结果：1、3、5、7、2、4、9
第二趟排序结果：1、2、5、7、3、4、9
第三趟排序结果：1、2、3、7、5、4、9
第四趟排序结果：1、2、3、4、5、7、9
第五趟排序结果：1、2、3、4、5、7、9
第六趟排序结果：1、2、3、4、5、7、9
这里分析一下复杂度，在最好的情况下，数字串本身就是有序的，则一次都不需要交换；在最坏的情况下，待排序字串是逆序的，则交换次数最多（次数是3(n-1)）。
选择排序的交换操作介于0和(n-1)次之间；比较操作为n(n-1)/2次之间；赋值操作介于0和3(n-1)次之间。比较次数与本身的序列是无关的，只与长度有关。所以进行比较的时间复杂度是O(N²)，而移动操作的时间复杂度是O(N)。实际上交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。
最后大家可以想想，这个选择排序还有没有什么可以优化的地方？
给大家提示一下，我们每次都是找最小的去交换，如果我们在里面每次都把最小的和最大的都找出来，一次交换两个呢？实际上这就是一个对选择排序的改进，二元选择排序算法。
本文原创于本人博客，请访问 http://irfen.me
©原创文章，转载请注明来源： 赵伊凡's Blog
©本文链接地址: 跟我学算法（五）——简单选择排序
“跟我学算法（五）——简单选择排序”的31个回复