上文:冒泡排序算法
背景
一组整型无序数组,通过选择排序算法进行排序,从小到大排序或者从大到小。
/**
* @author: csh
* @Date: 2021-08-29 21:31
* @Description:选择排序
*/
public class SelectionSort {
//数据
private static Integer[] intArr ={100,7,1,99,6,13,2,111};
public static void main(String[] args) {
for(int i = 0; i< intArr.length; i++){
//最小值坐标
int min=i;
for(int j = i+1; j< intArr.length-1; j++){
if(intArr[j]<intArr[min]){
min = j;
}
}
//进行交换
if(i!=min){
//存放数据第i个的值
int temp = intArr[i];
intArr[i] = intArr[min];
intArr[min] = temp;
System.out.println("第:"+(i+1)+"次排序"+Arrays.toString(intArr));
}
}
}
}
结果
第:1次排序[1, 7, 100, 99, 6, 13, 2, 111]
第:2次排序[1, 2, 100, 99, 6, 13, 7, 111]
第:3次排序[1, 2, 6, 99, 100, 13, 7, 111]
第:4次排序[1, 2, 6, 7, 100, 13, 99, 111]
第:5次排序[1, 2, 6, 7, 13, 100, 99, 111]
第:6次排序[1, 2, 6, 7, 13, 99, 100, 111]
通过上面数据可以得知,选择排序的实现原理是:
先获取第i位,然后通过子循环,判断当前位与接下来的数据匹配大小,如果小于则交换坐标到临时min中,直至子循环结束,然后再外循环进行交换数据。
时间复杂度和稳定性
由于遍历一次的复杂度为O(N),而遍历多少次取决于数组长度N-1,所以选择排序的时间复杂度为