数据结构与算法-排序（二）选择排序（Selection Sort）
数据结构与算法-排序（二）选择排序（Selection Sort）
摘要
选择排序的逻辑是先遍历比较出序列中最大的，然后把最大的放在最后位置。
遵循这个逻辑，用代码实现时，做到1.减少比较次数之外，这里引入一个新的指标 - 稳定性，2.保证排序过程中的稳定性也是一个优化处理
代码逻辑
从头遍历序列，分别和尾部元素比较，记录最大的元素坐标
遍历完成后，和尾部位置交换位置
忽略尾部已经交换的元素，执行 1 和 2 步骤
实现
依据逻辑来看，最大值是放在尾部，并放置后，下次循环排除这个放置最大值的位置，for 循环从尾部开始最合适。
小循环开始前，需要先创建变量记录最大值坐标，这里使用的是 0 位置坐标，那么小循环开始时，就可以直接从 1 位置遍历，这就减少比较次数。
for (int end = array.length-1; end > 0; end--) { int maxIndex = 0; for (int begin = 1; begin <= end; begin++) { if (cmp(maxIndex, begin) < 0) {
maxIndex = begin;
}
}
swap(maxIndex, end);
}进阶
开始前，先解释一下稳定性，稳定性是尽量保持序列中两个元素在排序前和排序后的相对位置。比如下面伪代码：
// a1 与 a2 的值相等a1 = a2 = 3// 序列中 a1 值的位置在 a2 前面array = [5, a1, 4, a2, 2]// 排序之后, a1 值位置在 a2 前面，保持了稳定性array = [2, a1, a2, 4, 5]
为什么稳定性重要？
序列中需要保证多次排序后数据位置的相对稳定。比如信息表中，以 age 从小到大排序，不希望 age 相等的一组数据中，它的名称在每一次排序之后都会有不同的顺序。
稳定性的优化
这里为了保证排序之后的稳定性，就当出现最大值时，也更新最大值的坐标。
为什么这样就可以保证稳定性？
首先最大值被交换到尾部之后，下次遍历比较的时候，就不再比较这个位置，小循环的比较是从头开始的，如果出现等于最大值时，不更新最大值的位置，排序之后，相等的值，最靠前的值就被放在了最后面，改变了之前序列中相等值的相对位置。
for (int end = array.length-1; end > 0; end--) { int maxIndex = 0; for (int begin = 1; begin <= end; begin++) { if (cmp(maxIndex, begin) <= 0) { // 保证稳定性
maxIndex = begin;
}
}
swap(maxIndex, end);
}时间和空间复杂度
最好、平均、最坏时间复杂度：O(n^2)，n 的 2 次方
空间复杂度：O(1)
属于稳定排序