选择排序

上一篇我们讲了冒泡排序，这次来讲下另外一种比较排序——选择排序。在代码实现上选择排序跟冒泡排序有点像。因为很多时候看到初学者往往都会把冒泡排序跟选择排序在代码上搞混。为什么像呢？看看下面实现原理及代码。

算法实现原理

直接选择排序：直接选择排序的作法是：第一趟扫描所有数据，选择其中最小的一个与第一个数据互换；第二趟从第二个数据开始向后扫描，选择最小的与第二个数据互换；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。

每一轮比较找到一个极值（最大值或最小值）放到某一端，对剩下的数再找极值，直至比较结束。

动图演示

代码实现

基本实现

优化实现：二元选择排序(1)

每次确定两个数（最大值和最小值），减少迭代次（用双循环实现不需要像下面的方法那样多重判断且考虑等值情况）

优化实现：二元选择排序（2）

使用单循环多判断实现

优化实现：等值情况

二元选择排序的时候，每一轮可以知道最大值和最小值，如果某一轮最大最小值都一样了，说明剩下的数字都是相等的，直接结束排序。

优化实现：等值情况优化

如果 = ,找到最大值索引为-5, 最小值索引为1，上面代码会交换两次，第二次的两个1交换是多余的操作，所以添加一个判断，如果值相同则不交换。

堆排序

堆排序实际上也是一种选择排序，但其时间复杂度是O（nlogn）。这涉及到二叉堆的知识，这里先不做详细介绍，后续会有专门讲解堆排序的文章。

时间复杂度

空间复杂度