写在前边的话：今天记录一下关于算法中简单选择排序的一些理解和心得。
主要分为以下几个方面分享
- 简单选择排序的思想
- 实现方式
- 时间复杂度
- 与冒泡排序的比较
简单选择排序的思想
1:给定一个具有n位数据的数组，拿 当前值与其后序列中的数据 进行比较， 如果此次遍历结束后发现 该序列中的最小(大)值比当前值还要小(大)，则交换2者的数据。
2:重复n-1次上述操作，直至该序列中所有数据满足降(升)序为止。
实现方式
public static void main(String[] args){
Integer[] array1 = Util.createRandomArray();
Integer[] array2 = Arrays.copyOf(array1, array1.length);
System.out.println("数据源：" + Arrays.toString(array1) + "---------------------------------");
selectSort(array1);
Util.print(array1 , "SelectSort");
Util.test(array2);
Util.print(array2, "Result ");
}
/**
* 简单选择排序
* @param src 数据源
*/
private static void selectSort(Integer[] src){
Util.checkSrc(src);
//参数说明
//i:需要从"哪个位置"开始执行后续的操作,该位置之前的序列已经是有序的了
//j:因为比较的是 i 和 其后序列中数的大小，所以 j初始化为i后一位
//curMinIndex:记录该次循环中最小值的下标
for(int i = 0; i < src.length; i++){ //n-1次循环
int curMinIndex = i; //初始化 当前最小值位置下标 为i
for(int j = i + 1; j < src.length; j++){ //swap循环。目的是为了找出:"从i位置开始的序列中最小的值"。
if(src[curMinIndex] > src[j]){ //如果存在的话,记录此值的下标
curMinIndex = j;
}
}
if(curMinIndex != i){ //swap操作。交换 i与curMinIndex下标所对应的值
int temp = src[i];
src[i] = src[curMinIndex];
src[curMinIndex] = temp;
}
}
}
查看log
数据源：[27, 4, 16, 70, 74, 86, 20, 19, 42, 13]
SelectSort:4---13---16---19---20---27---42---70---74---86
Result :4---13---16---19---20---27---42---70---74---86
时间复杂度
结论:O(n^2)
分析:假如有n=5个数要排序，总共需要执行n-1=4次循环操作
第1次：需要比较n-1=4次
第2次：需要比较n-2=3次
第3次：需要比较n-3=2次
第4次：需要比较n-4=1次
总共执行的次数为：n-1 + n-2 + ... + 2 + 1===>n^2/2，所以该排序的时间复杂度为:O(n^2)
与冒泡排序的比较
相同点：
1：时间复杂度都是O(n^2)。
2：一次循环只能确定出 一个最小(大)。
不同点：
结论
选择排序相较冒泡排序来说，时间复杂度虽然没有降低，但是减少了“数据交换”的次数。
原因
“简单选择排序”在swap循环中，如果发现有数据的值比当前值要小(大)，只是保存下该数据的下标，等该swap循环结束后再交换2者的值。
“冒泡排序”则是在swap循环中，如果发现有数据的值比当前值要小(大)，就直接交换。
