简单选择排序SimpleSelectSort
最后更新于：2022-04-01 09:49:18
冒泡排序：在每一次比较的时候，如果发现相邻两数的次序不对，都会马上就把两数进行对调。
选择排序：则在比较过程中（内循环里面）并不进行对调，而是先记录下最小（大）数的下标，在一次扫描完成后再进行对调。
1、算法思想
在要排序的一组数中，选出最小（或者最大）的一个数与第 i（i=0）个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第i+1个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
2、代码实现
~~~
/**
* 在要排序的一组数中，选出最小（或者最大）的一个数与第 i（i=0）个位置的数交换； 然后在剩下的数当中再找最小（或者最大）的与第i+1个位置的数交换， 依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
*/
private static void SimpleSelectSort(int[] source) {
if (source.length <= 1 || source == null) {// 习惯，参数判断
return;
}
for (int i = 0; i < source.length - 1; i++) { // i < source.length尚可
int j = i + 1;
int min = source[i]; // 最小值
int minIndex = i; // 最小值下标
while (j < source.length) {
if (source[j] < min) {
min = source[j];
minIndex = j;
}
j++;
}
if (minIndex != i) { // 3次赋值
source[i] = source[minIndex] + (source[minIndex] = source[i]) * 0;
}
printArr(source);
}
}
~~~
3、算法分析
1.时间复杂度
选择排序的交换操作介于 0 和 (n - 1）次之间。
选择排序的比较操作为 n (n - 1）/ 2次。
选择排序的赋值操作介于 0 和 3 (n - 1）次之间(n-1次交换，每次交换需要赋值3次) t = a, a = b, b = t。
比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+...+1=n*(n-1）/2。
交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。
交换次数比[冒泡排序](http://baike.baidu.com/view/254413.htm)少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。
2.稳定性
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。
4、算法改进
**二元选择排序**
简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。具体实现如下：（类冒泡）
~~~
/**
* 简单选择排序，每趟循环只能确定一个元素排序后的定位。 我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置。 从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。
*/
private static void TwoSelectSort(int[] source) {
int n = source.length;
if (n <= 1 || source == null) {// 习惯，参数判断
return;
}
int minIndex, maxIndex, tempI;
for (int i = 0; i < n / 2; i++) {
minIndex = maxIndex = i;
for (int j = i + 1; j < n - i; j++) {
if (source[j] < source[minIndex]) {
minIndex = j;
continue;
}
if (source[j] > source[maxIndex]) {
maxIndex = j;
}
}
if (minIndex != i) { // 3次赋值
source[i] = source[minIndex] + (source[minIndex] = source[i]) * 0;
}
if (maxIndex == i) { // 此时最大值已被替换到minIndex处
maxIndex = minIndex;
}
if (maxIndex != n - i - 1) {
source[n - i - 1] = source[maxIndex] + (source[maxIndex] = source[n - i - 1]) * 0;
}
printArr(source);
}
}
~~~
冒泡排序改进算法之每趟循环确定两个元素时，不用考虑 if（maxIndex==i），因为其每趟比较只要不符合排序就要交换位置，而不是仅仅记录其索引的改变。
源码地址：[https://github.com/zxiaofan/Algorithm/blob/master/src/sort/SelectSort.java](https://github.com/zxiaofan/Algorithm/blob/master/src/sort/SelectSort.java)